题目描述

你有一个从 $1$ 到 $n$ 的整数排列 $P$ 。

对于所有 $i=1,2,\dots,N$ ，输出满足以下所有条件的一对整数 $(l,r)$ 的 $r-l+1$ 的最小值。如果不存在这样的 $(l,r)$ ，则输出 -1 。

• $1 \le l \le i \le r \le N$ 。
• $r-l+1$ 是奇数。
• $P_i$ 不是 $P$ 的子序列 $(P_l,P_{l+1},\dots,P_r)$ 的中位数。

长度为 $L$（奇数）的整数序列 $A$ 的中位数被定义为按升序对 $A$ 排序后的序列 $A'$ 的第 $\frac{L+1}{2}$ 个值。

输入格式

输入来自标准输入，以 $N$ $P_1$ $P_2$ $\dots$ $P_N$ 的格式输入。

输出格式

输出 $i=1,2,\dots,N$ 的答案，用空格隔开。

样例解释1

例如，当 $i=2$ 时，若 $(l,r)=(2,4)$ ，则 $r-l+1=3$ ，为奇数，且 $(P_2,P_3,P_4)=(3,5,4)$ 的中位数是 $4$ ，不是 $P_2$ ，满足条件, 因此答案是 $3$ 。
当 $i=4$ 时，$(l,r)=(4,4),(2,4),(3,5)$ 的中位数都是 $P_4=4$ 。 若 $(l,r)=(1,5)$ ，则 $(P_1,P_2,P_3,P_4,P_5)=(1,3,5,4,2)$ 的中位数为 $3$ ，不是 $P_4$ ，满足条件,因此答案是 $5$ 。

样例解释2

$i=1$ 时，不存在满足条件的整数组 $(l,r)$ 。

数据规模与约定

• $3 \le N \le 3 \times 10^5$。
• $(P_1,P_2,\dots,P_N)$ 是从 $1$ 到 $n$ 的整数排列。
• 所有输入值都是整数。

样例 1

输入

5
1 3 5 4 2

输出

3 3 3 5 3

样例 2

输入

3
2 1 3

输出

-1 3 3

样例 3

输入

14
7 14 6 8 10 2 9 5 4 12 11 3 13 1

输出

5 3 3 7 3 3 3 5 3 3 5 3 3 3