/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの整数からなる長さ N の順列 P=(P_1,P_2,\dots,P_N) が与えられます。
各 i=1,2,\dots,N に対し、以下の条件をすべて満たす 2 つの整数の組 (l,r) に対する r-l+1 の最小値を出力してください。ただし、そのような (l,r) が存在しない場合は -1 を出力してください。
- 1 \leq l \leq i \leq r \leq N
- r-l+1 は奇数
- P の連続部分列 (P_l,P_{l+1},\dots,P_r) の中央値は P_i ではない
ここで、長さが L （奇数）の整数列 A に対して A の中央値とは、 A を昇順にソートして得られる数列を A' として A' の \frac{L+1}{2} 番目の値のことを指します。
制約
- 3 \leq N \leq 3 \times 10^5
- (P_1,P_2,\dots,P_N) は 1 から 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) の中央値は 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 です。
入力例 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
Score: 600 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of integers from 1 to N.
For each i=1,2,\dots,N, print the minimum value of r-l+1 for a pair of integers (l,r) that satisfies all of the following conditions. If no such (l,r) exists, print -1.
- 1 \leq l \leq i \leq r \leq N
- r-l+1 is odd.
- The median of the contiguous subsequence (P_l,P_{l+1},\dots,P_r) of P is not P_i.
Here, the median of A for an integer sequence A of length L (odd) is defined as the \frac{L+1}{2}-th value of the sequence A' obtained by sorting A in ascending order.
Constraints
- 3 \leq N \leq 3 \times 10^5
- (P_1,P_2,\dots,P_N) is a permutation of integers from 1 to N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N
Output
Print the answers for i=1,2,\dots,N in this order, separated by spaces.
Sample Input 1
5 1 3 5 4 2
Sample Output 1
3 3 3 5 3
For example, when i=2, if we set (l,r)=(2,4), then r-l+1=3 is odd, and the median of (P_2,P_3,P_4)=(3,5,4) is 4, which is not P_2, so the conditions are satisfied. Thus, the answer is 3.
On the other hand, when i=4, the median of (P_l,\dots,P_r) for any of (l,r)=(4,4),(2,4),(3,5) is P_4=4. If we set (l,r)=(1,5), the median of (P_1,P_2,P_3,P_4,P_5)=(1,3,5,4,2) is 3, which is not P_4, so the conditions are satisfied. Thus, the answer is 5.
Sample Input 2
3 2 1 3
Sample Output 2
-1 3 3
When i=1, no pair of integers (l,r) satisfies the conditions.
Sample Input 3
14 7 14 6 8 10 2 9 5 4 12 11 3 13 1
Sample Output 3
5 3 3 7 3 3 3 5 3 3 5 3 3 3