沃尔夫冈·阿玛多伊斯·莫扎特（Wolfgang Amadeus Mozart）有太多的钥匙了！他的环形钥匙扣上有 $n$ 把长度互不相同的钥匙。不幸的是，沃尔夫冈只能通过一把钥匙与它周围钥匙的相对大小关系，来判断它是否能开门。

设钥匙 $x$ 的 $k$-模式（$k$-pattern）为：在钥匙扣上沿顺时针方向紧随钥匙 $x$ 之后的 $k$ 把钥匙的相对长度序列。例如，如果钥匙扣上的钥匙长度按顺时针顺序依次为 1, 5, 3, 4, 2，那么长度为 3 的钥匙的 3-模式可以表示为字符串 "<>>"，因为 $3 < 4$，$4 > 2$，且 $2 > 1$。请注意，最后一把长度为 2 的钥匙后面紧跟着第一把长度为 1 的钥匙。

请帮助沃尔夫冈确定每把钥匙的最小 $k$，使得该钥匙的 $k$-模式是唯一的（即没有其他钥匙具有相同的 $k$-模式）。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示沃尔夫冈环形钥匙扣上的钥匙数量。

接下来的 $n$ 行，每行包含一个介于 $1$ 和 $10^9$ 之间的整数，表示一把钥匙的长度。钥匙的长度是按钥匙扣上的顺时针顺序给出的。保证所有钥匙的长度互不相同。

输出格式

输出 $n$ 行，每行一个整数。第 $i$ 个整数应当是使得第 $i$ 把钥匙（按输入顺序）的 $k$-模式在所有 $k$-模式中唯一的最小 $k$。如果不存在这样的 $k$，则第 $i$ 个整数应当为 $-1$。

样例

输入样例 1

5
1
8
3
4
2

输出样例 1

3
4
3
2
4

输入样例 2

4
1
4
2
3

输出样例 2

-1
-1
-1
-1