問題一覧 > 通常問題

No.2223 Merged Med

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : stoq / テスター : nok0 Shirotsume
お気に入りにしたユーザー ProblemId : 7697 / 自分の提出
問題文最終更新日: 2023-02-17 21:52:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 377 (順位表) の他の問題:

Problem Statement

The beauty of a sequence $X=(X_1,\dots,X_k)$ is defined as follows.

  • Choose $(l,r) \ (1 \leq l \leq r \leq k)$ and create a sequence $X'$ of length $k+l-r$ by replacing $X_l,\dots,X_r$ in $X$ with the single element ${\rm Med}(X_l,\dots ,X_r)$.
    The beauty of $X$ is the minimum value of ${\rm Med}(X')$ over all possible such $X'$.

Here, for $Y=(Y_1,\dots,Y_k)$, ${\rm Med}(Y)$ denotes the median of $Y_1,\dots,Y_k$, that is, the $\displaystyle \left \lfloor \frac{k}{2} \right \rfloor +1$-th element when $Y_1,\dots,Y_k$ are sorted in ascending order.

You are given a sequence $(A_1,\dots,A_N)$ of length $N$.

Process the following $Q$ queries.

$l$ $r$
  • Output the beauty of the sequence $(A_l,\dots,A_r)$.

Input

$N$ $Q$
$A_1$ $\dots$ $A_N$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$

  • All input values are integers.
  • $1 \leq N \leq 5 \times 10^4$
  • $1 \leq Q \leq 5 \times 10^4$
  • $1 \leq A_i \leq N$
  • $1 \leq l_i \leq r_i \leq N$

Output

Output the answer to each query, separated by newlines.

Sample

Sample 1
Input
5 3
1 5 3 4 2
1 5
2 3
1 1
Output
2
5
1

For the $1$st query, for example, replacing $A_2,A_3,A_4$ with their median gives $(1,\ 4,\ 2)$, whose median is $2$.
There is no way to make the median smaller than this, so the beauty of $(A_1,\dots,A_5)$ is $2$.

For the $2$nd query, for example, replacing $A_2,A_3$ with their median gives $(5)$, whose median is $5$.
There is no way to make the median smaller than this, so the beauty of $(A_2,A_3)$ is $5$.

Sample 2
Input
3 3
3 3 3
1 3
2 3
3 3
Output
3
3
3

$A_i$ are not necessarily distinct.

Sample 3
Input
20 10
1 6 6 19 13 10 20 1 8 11 12 4 7 3 10 20 19 13 14 13
1 20
2 13
6 7
5 16
9 13
12 14
11 13
10 13
2 14
6 17
Output
6
6
20
10
7
4
7
7
6
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。