← 返回题目列表

AtCoder · arc173_c

C. 不是中位数

中文机器翻译题面 查看原题

分数: 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