TopCoder

User's AC Ratio

35.0% (7/20)

Submission's AC Ratio

27.4% (17/62)

Tags

Description

老鼠是個天才兒童,在三歲時養了一隻貓咪,在五歲時學會了 LCT,七歲時成功用魔法趕走了兇巴巴的史萊姆,最近則順利拿到書卷獎。
貓咪每天都要舉 1000kg 的槓鈴,只是今天老鼠把槓鈴放在磅秤上後,發現槓鈴竟然少了 24g。

於是老鼠帶貓咪去地下格鬥場,總共有 n+1 個選手,編號為 0n
編號 i0in)的選手的體力為 ai,一開始編號 0 的選手為衛冕者,剩下的選手會按照編號由小到大依序向衛冕者挑戰。

假設衛冕者的體力為 x,挑戰者的體力為 y,若 xy,則挑戰者挑戰失敗,衛冕者繼續衛冕,且體力變成 xy;若 x<y,則挑戰者挑戰成功,成為衛冕者,且體力變成 yx

a1an 是固定的,但是 a0 會隨著編號 0 參賽者的心情改變,貓咪總共有 q 個疑問:如果編號 0 的參賽者體力是 a0,並且現在編號 p 的選手挑戰完了,那麼此時衛冕者的體力是多少?

Input Format

第一行有兩個正整數 n,q,代表有 n+1 位選手和 q 個疑問。
第二行有 n 個非負整數 a1an,代表編號 1n 選手的體力。
接下來 q 行,每行有一個非負整數和一個正整數 a0,p,代表編號 0 選手的體力和現在編號 p 的選手挑戰完了。

對於所有測試資料:

  • 1n,q106
  • 0ai1061in
  • 0a0106
  • 1pn

Output Format

對於每個疑問,回答若編號 0 的參賽者體力是 a0,且現在編號 p 的選手挑戰完了,此時衛冕者的體力是多少。

Sample Input 1

3 4
7 10 2
2 1
13 2
20 2
5 3

Sample Output 1

5
4
3
6

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 n,q3000 17
3 1, 6~10 aiai+10i<n 19
4 0~15 無其他限制 64

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 65536 1 2 4
1 2500 262144 65536 2 3 4
2 2500 262144 65536 2 4
3 2500 262144 65536 2 4
4 2500 262144 65536 2 4
5 2500 262144 65536 2 4
6 2500 262144 65536 3 4
7 2500 262144 65536 3 4
8 2500 262144 65536 3 4
9 2500 262144 65536 3 4
10 2500 262144 65536 3 4
11 2500 262144 65536 4
12 2500 262144 65536 4
13 2500 262144 65536 4
14 2500 262144 65536 4
15 2500 262144 65536 4