Increasing Sequence

각 i마다 다른 원소 j 하나를 제거했을 때 i를 포함하는 최장 증가 부분 수열의 길이가 줄어드는 j의 개수를 구한다.

어려움9동적 계획법세그먼트 트리조합론이분 탐색아직 제출이 없습니다시간 제한3초메모리 제한1024 MB

문제 설명

예제5

문제

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

The next line contains $N$ integers $A\_1, A\_2, \cdots, A\_N$ .

출력

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

제한

$1 \leq N \leq 250\\,000$
$1 \le A\_i \le N$
Every element of $A$ is distinct.