열쇠 찾기

시간 제한2초메모리 제한2048 MB

요약

원형 열쇠고리의 열쇠마다, 뒤따르는 k개 열쇠와의 크기 비교 패턴이 다른 열쇠와 겹치지 않는 최소 k를 구합니다.

난이도: 보통10점 중 7점
유형: 문자열, 문자열 매칭, 정렬
정답자: 아직 제출이 없습니다

문제

모차르트는 열쇠가 너무 많다! 그는 원형 열쇠고리에 길이가 서로 다른 $n$ 개의 열쇠를 달아 두었다. 안타깝게도 모차르트는 열쇠가 문에 맞는지를 주변 열쇠와의 상대적인 길이로만 판단할 수 있다.

열쇠 $x$ 의 $k$ -패턴은 열쇠고리에서 $x$ 다음에 시계 방향으로 이어지는 $k$ 개 열쇠의 상대적인 길이 순서로 정의한다. 예를 들어 열쇠고리에 시계 방향으로 길이 1, 5, 3, 4, 2인 열쇠가 있다면, 길이 3인 열쇠의 3-패턴은 "<>>"이다. 3 < 4, 4 > 2, 2 > 1이기 때문이다. 길이 2인 마지막 열쇠 다음에는 길이 1인 첫 번째 열쇠가 온다.

각 열쇠마다 그 $k$ -패턴이 유일해지는 가장 작은 $k$ 를 구한다. 유일하다는 것은 다른 열쇠 중 같은 $k$ -패턴을 가진 열쇠가 없다는 뜻이다. 그런 $k$ 가 없으면 -1을 출력한다.

입력

첫 줄에 열쇠의 개수 $n$ ( $2 \le n \le 2 \cdot 10^5$ )이 주어진다. 다음 $n$ 개 줄에는 각각 1 이상 $10^9$ 이하의 정수가 하나씩 주어지며, 시계 방향 순서대로 열쇠의 길이를 나타낸다. 모든 열쇠의 길이는 서로 다르다.

출력

$n$ 개의 줄에 정수를 한 줄에 하나씩 출력한다. $i$ 번째 정수는 입력에서 $i$ 번째 열쇠의 $k$ -패턴이 유일해지는 가장 작은 $k$ 이다. 그런 $k$ 가 없으면 -1을 출력한다.

예제2

예제 1
입력
```
5
1
8
3
4
2
```
예상 출력
```
3
4
3
2
4
```
예제 2
입력
```
4
1
4
2
3
```
예상 출력
```
-1
-1
-1
-1
```