시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (언어별 추가 시간 없음) 1024 MB 52 7 5 41.667%

문제

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.

서브태스크 1 (22점)

This subtask has an additional constraint:

  • $N \le 100$

서브태스크 2 (17점)

This subtask has an additional constraint:

  • $N \le 2\,000$

서브태스크 3 (61점)

This subtask has no additional constraints.

예제 입력 1

1
1

예제 출력 1

0

예제 입력 2

6
1 2 3 4 5 6

예제 출력 2

5 5 5 5 5 5

예제 입력 3

6
6 5 4 3 2 1

예제 출력 3

0 0 0 0 0 0

예제 입력 4

4
2 1 4 3

예제 출력 4

0 0 0 0

예제 입력 5

9
1 2 3 6 5 4 7 8 9

예제 출력 5

5 5 5 6 6 6 5 5 5

출처

University > KAIST > 2019 KAIST RUN Spring Open Contest G번

채점

  • 예제는 채점하지 않는다.