Finding Keys

Time limit2sMemory limit2048 MB

Summary

For each key on a circular keychain, find the smallest k whose k-pattern of up and down comparisons with the next k keys no other key shares.

Level: Medium7 of 10
Topics: String, String matching, Sorting
Solved: No attempts yet

Problem

Wolfgang Amadeus Mozart has too many keys! He has $n$ keys of distinct lengths on his circular keychain. Unfortunately, Wolfgang can only judge whether a key fits into a door by its relative size compared to the keys around it.

Let the $k$ -pattern of a key $x$ be the sequence of relative lengths of the $k$ keys that follow key $x$ in clockwise order. For example, if the keychain has keys of lengths 1, 5, 3, 4, 2 in clockwise order, then the 3-pattern of the key of length 3 is "<>>", since 3 < 4, 4 > 2, and 2 > 1. The last key of length 2 is followed by the first key of length 1.

For each key, find the smallest $k$ such that its $k$ -pattern is unique, meaning no other key has the same $k$ -pattern. If no such $k$ exists, output -1.

Input

The first line contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ), the number of keys. Each of the next $n$ lines contains one integer between 1 and $10^9$ , the length of a key, in clockwise order. All key lengths are distinct.

Output

Output $n$ lines, one integer per line. The $i$ th integer is the smallest $k$ such that the $k$ -pattern of the $i$ th key in the input is unique. If no such $k$ exists, output -1.

Examples2

Example 1
Input
```
5
1
8
3
4
2
```
Expected output
```
3
4
3
2
4
```
Example 2
Input
```
4
1
4
2
3
```
Expected output
```
-1
-1
-1
-1
```