405989: GYM102202 G Increasing Sequence

Memory Limit：1024 MB Time Limit：3 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

G. Increasing Sequencetime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a permutation of size $$$N$$$. For each $$$i$$$, print the number of indices $$$j \neq i$$$, which when removed, decreases the maximum possible length of an increasing subsequence that contains index $$$i$$$.

Input

The first line contains an integer $$$N$$$. ($$$1 \le N \le 250000$$$).

The next line contains $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ denoting the permutation. ($$$1 \le A_i \le N$$$, all $$$A_i$$$s are distinct).

Output

Print $$$N$$$ integers, separated by spaces, denoting the answers for $$$i = 1, 2, 3, \cdots, N$$$.

ExamplesInput
1
1
Output
0
Input
6
1 2 3 4 5 6
Output
5 5 5 5 5 5
Input
6
6 5 4 3 2 1
Output
0 0 0 0 0 0
Input
4
2 1 4 3
Output
0 0 0 0
Input
9
1 2 3 6 5 4 7 8 9
Output
5 5 5 6 6 6 5 5 5

Source/Category

加入题单

上一题 下一题 算法标签：