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

### 制約 - $ 3\ \leq\ N\ \leq\ 3\ \times\ 10^5 $ - $ (P_1,P_2,\dots,P_N) $ は $ 1 $ から $ N $ までの整数からなる順列 - 入力される値はすべて整数 ### Sample Explanation 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_l,\dots,P_r) $ の中央値は常に $ 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 $ です。 ### Sample Explanation 2 $ i=1 $ のとき、条件を満たす整数の組 $ (l,r) $ は存在しません。