题目描述

给定一个大小为 $N$ 的排列。对于每个 $i$，输出满足以下条件的下标 $j$（$j \neq i$）的数量：当移除下标 $j$ 后，会使得包含下标 $i$ 的最长上升子序列的最大可能长度减少。

输入格式

第一行包含一个整数 $N$。 ($1 \le N \le 250000$)

第二行包含 $N$ 个整数 $A_1, A_2, \cdots, A_N$，表示该排列。 ($1 \le A_i \le N$，所有 $A_i$ 互不相同)

输出格式

输出 $N$ 个整数，以空格分隔，表示对于 $i = 1, 2, 3, \cdots, N$ 的答案。

1
1

0

6
1 2 3 4 5 6

5 5 5 5 5 5

6
6 5 4 3 2 1

0 0 0 0 0 0

4
2 1 4 3

0 0 0 0

9
1 2 3 6 5 4 7 8 9

5 5 5 6 6 6 5 5 5

提示

翻译由 DeepSeek 完成