증가하는 수열

시간 제한3초메모리 제한1024 MB

요약

순열이 주어질 때, 각 인덱스 i마다 j를 제거하면 i를 포함하는 최장 증가 부분 수열의 길이가 줄어드는 j(j≠i)의 개수를 구합니다.

문제

길이가 $N$ 인 순열이 주어진다. 각 $i$ 에 대해, $j \neq i$ 인 인덱스 $j$ 중에서 그 원소를 제거하면 인덱스 $i$ 를 포함하는 증가하는 부분 수열의 최대 길이가 줄어드는 $j$ 의 개수를 구한다.

첫 번째 줄에 정수 $N$ 이 주어진다.

두 번째 줄에는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 주어진다.

$N$ 개의 정수를 공백으로 구분하여 출력한다. $i$ 번째 정수는 인덱스 $i$ 에 대한 답이다.