32846번 - Finding Keys 다국어

문제

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 surrounding it. Let the $k$-pattern of a key $x$ be the sequence of relative key lengths of the $k$ keys following key $x$ in clockwise order on the keychain. For example, if keychain has keys of lengths 1,ドル 5, 3, 4, 2$ in clockwise order, then the 3ドル$-pattern of the key of length 3ドル$ can be expressed as the string “<>>”, since 3ドル$ < 4ドル,ドル 4ドル$ > 2ドル,ドル and 2ドル$ > 1ドル$. Note that the last key of length 2ドル$ is followed by the first key of length 1ドル$.

Please help Wolfgang determine for each key the smallest $k$ such that the $k$-pattern of the key is unique (no other key’s $k$-pattern is the same).

입력

The first line of input contains a single integer $n$ (2ドル ≤ n ≤ 2 \cdot 10^5$), the number of keys on Wolfgang’s circular keychain.

The next $n$ lines each contain an integer between 1ドル$ and 10ドル^9$ representing the length of one key. The key lengths are given in their clockwise order on the keychain. It is guaranteed that all key lengths are unique.

출력

Output $n$ lines, one integer per line. The $i$^th integer should be the smallest $k$ such that the $k$-pattern of key $i$ (in input order) is unique among all $k$-patterns. If there exists no such $k,ドル then the $i$^th integer should be $-1$.

제한

힌트