Not Median

时间限制：2s
空间限制：512MB

题目描述

给定一个长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，其中包含 $1$ 到 $N$ 的每个整数恰好一次。

对每个 $i=1,2,\ldots,N$，请求出满足以下所有条件的整数对 $(l,r)$ 中 $r-l+1$ 的最小值：

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

如果不存在这样的 $(l,r)$，则输出 $-1$。

对于长度为奇数 $L$ 的整数序列 $A$，将其按升序排列得到 $A'$，则 $A$ 的中位数定义为 $A'$ 中第 $\frac{L+1}{2}$ 个数。

输入格式

从标准输入读入数据，格式如下：

$N$

$P_1\ P_2\ \ldots\ P_N$

输出格式

依次输出 $i=1,2,\ldots,N$ 的答案，相邻答案之间用一个空格分隔。

样例输入 1

5
1 3 5 4 2

样例输出 1

3 3 3 5 3

样例解释 1

当 $i=2$ 时，取 $(l,r)=(2,4)$，子序列 $(3,5,4)$ 的中位数为 $4$，不是 $P_2=3$，因此答案为 $3$。

当 $i=4$ 时，长度为 $1$ 或 $3$ 的可选区间都以 $P_4=4$ 为中位数；取 $(l,r)=(1,5)$ 时中位数为 $3$，故答案为 $5$。

样例输入 2

3
2 1 3

样例输出 2

-1 3 3

样例解释 2

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

样例输入 3

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

样例输出 3

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

数据范围

• $3\le N\le 3\times 10^5$；
• $P$ 是 $1$ 到 $N$ 的一个排列；
• 输入中的所有数均为整数。