Stikl

숫자 타일, 게랄트 제공, Pixabay

당신은 친구와 게임하는 것을 좋아한다. 요즘 두 사람이 가장 좋아하는 게임은 Stikl이다. 먼저 $n$개의 칸을 한 줄로 놓고, 각 칸에 임의의 숫자를 하나씩 쓴다. 게임의 규칙은 간단하다. 두 플레이어는 모두 임의의 칸에서 시작한다. 그런 다음 번갈아 주사위를 던지고, 그 결과에 따라 정해진 횟수만큼 이동한다. 각 이동에서 플레이어는 현재 있는 칸에 적힌 숫자보다 작지 않은 숫자가 적힌 오른쪽의 첫 번째 칸으로 이동한다. 이 게임에서 가장 어려운 점은 플레이어가 일정 횟수만큼 이동한 뒤 어디에서 끝나는지 알아내는 것이다.

점수

그룹 | 점수 | 제한

1 | 42 | $n, q \leq 100$

2 | 26 | $s$은 항상 $1$이다

3 | 32 | 추가 제한 없음

첫째 줄에 칸의 수와 질의의 수를 나타내는 두 정수 $n$과 $q$가 주어진다 ($1 \leq n, q \leq 10^5$). 둘째 줄에 왼쪽부터 오른쪽까지 각 칸에 적힌 숫자를 나타내는 $n$개의 정수 $a_1,a_2,\ldots,a_n$가 주어진다 ($1 \leq a_i \leq 10^9$). 이어서 $q$개의 질의가 주어지며, 각 질의는 두 정수 $s$와 $d$을 포함하는 한 줄로 이루어진다 ($1 \leq s \leq n$, $1 \leq d \leq 10^5$). 이들은 각각 플레이어가 시작하는 칸의 번호와 이동하는 횟수를 나타낸다.

각 질의마다 플레이어가 $s$번 칸에서 시작하여 $d$번 이동했을 때 도착하는 칸의 번호를 한 줄에 출력한다. 플레이어가 칸의 끝을 넘어가게 된다면, 해당 질의에 대해 ```leik lokid`''을 출력한다.