問題
1부터 N까지의 숫자가 적혀있는 카드 더미가 있다. 이때 N은 항상 짝수이다. 더미의 가장 아래는 첫번째 숫자 카드가 있고, 가장 위에는 마지막 숫자 카드가 위치해 있도록 순서대로 배치되어 있다.
한번의 "셔플"이란, 카드 더미의 중앙을 기준으로 분리한 뒤, 가장 아래 있는 카드에 적혀있는 수 두 개를 비교하여 더 작은 카드를 내려놓는 방식으로 진행된다.
예를 들어, "1 5 6 2 3 4"를 분리하면 "1 5 6"과 "2 3 4"가 되고, 작은 카드부터 내려놓게되면 "1 2 3 4 5 6"이 된다.
총 Q개의 쿼리를 처리하는데, i번 쿼리는 셔플을 ai번 진행한 뒤 bi번 위치에 있는 카드의 번호를 구하는 것이다.
각 쿼리에 대한 답을 구하시오.
輸入
첫 줄에 N과 Q가 주어진다. (2<=N<=2*10^5, 1<=Q<=10^6)
그 다음 줄에 카드 더미의 초기 상태를 나타내는 길이 N의 순열이 들어온다. 앞에 있는 수가 가장 아래에 있는 수이다.
그 다음 Q개 줄에 걸쳐 쿼리를 나타내는 두 정수 ai, bi가 주어진다. (0<=ai<=10^9, 1<=bi<=N)
輸出
Q개의 줄에 걸쳐, i번째 줄에는 ai번 셔플을 진행한 후 bi번 위치에 있는 카드의 번호를 출력해라.
子任務
| 編號 | 分數 | 條件 |
|---|---|---|
| #1 | 11分 | N<=1000 |
| #2 | 41分 | a1=a2=...=aQ |
| #3 | 31分 | N<=100000, Q<=100000 |
| #4 | 17分 | 제한 없음 |
範例 #1
6 3
1 5 6 2 3 4
1 2
0 4
1 5
2
2
5
範例 #2
6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
2
2
5
4
3
3
範例 #3
10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
2
3
6
1
7
5
8
4
9
10
來源
CEOI 2022 Day1
需要登入才能撰寫程式碼。