405981: GYM102201 I Increasing Sequence

I. 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