P15635 [2019 KAIST RUN Spring] Increasing Sequence

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

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

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