分数: 600 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) 的整数来自 1 to N.
对于每个 i=1,2,\dots,N,打印最小值 r-l+1 为一对整数 (l,r) 满足以下所有条件。如果没有这样的 (l,r) 存在,打印 -1.
- 1 \leq l \leq i \leq r \leq N
- r-l+1 是奇数。
- 连续子序列的中位数 (P_l,P_{l+1},\dots,P_r) of P is 不 P_i.
这里,中位数 A 对于整数序列 A 长度 L (奇数)被定义为 \frac{L+1}{2}序列的第一个值 排序得到 A' 通过排序得到 A 按升序排列。
约束
- 3 \leq N \leq 3 \times 10^5
- (P_1,P_2,\dots,P_N) 是来自以下整数的排列 1 to N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \dots P_N
输出
打印以下问题的答案 i=1,2,\dots,N 按此顺序,用空格分隔。
示例输入 1
5 1 3 5 4 2
示例输出 1
3 3 3 5 3
例如,当 i=2,如果我们设置 (l,r)=(2,4),那么 r-l+1=3 是奇数,并且中位数 (P_2,P_3,P_4)=(3,5,4) is 4,这不是 P_2,因此满足条件。因此,答案是 3.
另一方面,当 i=4,中位数 (P_l,\dots,P_r) 对于任何 (l,r)=(4,4),(2,4),(3,5) is P_4=4。如果我们设置 (l,r)=(1,5),中位数 (P_1,P_2,P_3,P_4,P_5)=(1,3,5,4,2) is 3,这不是 P_4,因此满足条件。因此,答案是 5.
示例输入 2
3 2 1 3
示例输出 2
-1 3 3
当 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