题目描述

莫扎特有太多钥匙了！他有 $n$ 把长度互不相同的钥匙，挂在一个环形钥匙圈上。

不幸的是，莫扎特只能通过一把钥匙与它周围钥匙的相对大小来判断它是否能开门。定义一把钥匙 $x$ 的 $k$-模式为：从钥匙 $x$ 开始，顺时针方向接下来的 $k$ 对相邻钥匙长度的大小关系序列。

例如，若钥匙圈上的钥匙长度顺时针依次为：

那么长度为 $3$ 的钥匙的 $3$-模式可以表示为字符串 <> > 去掉空格后即 <>>，因为：

注意，最后一把钥匙后面跟着第一把钥匙。

请你对每一把钥匙，求出最小的 $k$，使得这把钥匙的 $k$-模式在所有钥匙的 $k$-模式中是唯一的。如果不存在这样的 $k$，输出 $-1$。

输入格式

第一行包含一个整数 $n$：

接下来 $n$ 行，每行包含一个整数，表示一把钥匙的长度。钥匙按顺时针顺序给出，长度在 $1$ 到 $10^9$ 之间，且互不相同。

输出格式

输出 $n$ 行。第 $i$ 行输出第 $i$ 把钥匙的答案：最小的 $k$，使得第 $i$ 把钥匙的 $k$-模式唯一。若不存在，输出 $-1$。

样例 #1

输入 #1

5
1
8
3
4
2

输出 #1

3
4
3
2
4

样例 #2

输入 #2

4
1
4
2
3

输出 #2

-1
-1
-1
-1