Problem Description

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 Format

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 Format

Print $N$ integers, separated by spaces, denoting the answers for $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