問題一覧 > 通常問題

No.2077 Get Minimum Algorithm

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : chineristACchineristAC / テスター : HYEA LEEHYEA LEE
3 ProblemId : 7409 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 23:29:58

問題文

長さ $N$ で $1$ から $N$ までの整数からなる順列 $P=(P_1,\ P_2,\ \dots,\ P_N)$ があります。

次のような操作を考えます。

操作

  • $1.$ $X=N+1,\ i=1$ で初期化する
  • $2.$ $X\leftarrow \min(X,\ P_i),\ P_i\leftarrow \max(X,\ P_i)$ で同時に更新する
  • $3.$ $i=N$ ならば操作を終える。そうでないなら $i\leftarrow i+1$ と更新し、 $2$ に戻る。

$P$ に対し操作を $k$ 回適用したあとの数列 $P$ を $P_k=(P_{k,1},\ P_{k,2},\ \dots,\ P_{k,N})$ とします。

$Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは $2$ つの整数 $x_i,\ y_i\ (x_i < y_i)$ が与えられるので $P_{x_i,k}=y_i$ を満たす $k$ を出力してください(このような $k$ は必ず存在することが示せます)。

入力

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_Q$ $y_Q$
  • $1 \le N \le 10^5$
  • $1 \le P_i \le N$
  • $i\neq j$ ならば $P_i \neq P_j$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le x_i< y_i \le N$
  • 与えられる入力はすべて整数

出力

$Q$ 行出力してください。 $i$ 行目には $P_{x_i,k}=y_i$ を満たす $k$ を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
5
2 5 3 1 4
2
1 2
2 5
出力
4
3

$P_1=(6,\ 5,\ 3,\ 2,\ 4)$ になり、特に $P_{1,4}=2$ です。よって $1$ 回目のクエリでは $4$ を出力します。

また、$P_2=(6,\ 6,\ 5,\ 3,\ 4)$ になり、特に $P_{2,3}=5$ です。よって $2$ 回目のクエリでは $3$ を出力します。

サンプル2
入力
5
1 2 3 4 5
2
1 3
3 5
出力
3
5

サンプル3
入力
20
20 19 9 15 18 16 13 14 17 12 11 10 6 5 8 4 2 3 7 1
10
4 6
13 19
10 19
14 17
11 15
9 10
10 15
2 9
3 18
7 14
出力
18
15
12
18
17
20
16
14
6
14

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