AT_arc173_c.[ARC173C] Not Median

你有一个从 $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$ 的整数排列。
• 所有输入值都是整数。