Có $n$ kiện hàng, được đánh số từ $1$ đến $n$, vừa mới được chuyển đến một nhà kho. Chúng đến theo thứ tự $a_1, \dots, a_n$, và ta muốn sắp xếp chúng sao cho chúng có thứ tự $1, 2, \dots, n$.

Cỗ máy phân loại trong nhà kho hoạt động theo từng giai đoạn. Mỗi giai đoạn nhận vào một hàng kiện hàng $a_1, \dots, a_n$ và thực hiện như sau: Đầu tiên, kiện hàng thứ nhất $a_1$ được đặt vào một hàng mới. Sau đó, với mỗi kiện hàng $a_i$ với $i = 2, \dots, n$, nếu $a_i$ lớn hơn kiện hàng cuối cùng (ngoài cùng bên phải) trong hàng mới, máy sẽ đặt nó vào cuối hàng. Ngược lại, máy đặt nó vào đầu hàng.

Nếu hàng mới vẫn chưa được sắp xếp tăng dần, nó sẽ trở thành đầu vào cho giai đoạn tiếp theo của cỗ máy phân loại.

Hãy viết chương trình giúp kiểm tra xem cỗ máy có hoạt động đúng như thiết kế hay không bằng cách trả lời các truy vấn có dạng "kiện hàng nào nằm ở vị trí thứ $b$ sau $t$ giai đoạn".

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 5 \cdot 10^5$), lần lượt biểu thị số lượng kiện hàng và số lượng truy vấn.

Dòng thứ hai chứa một dãy gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) biểu thị thứ tự ban đầu của các kiện hàng.

$q$ dòng tiếp theo chứa các truy vấn; dòng thứ $i$ chứa hai số nguyên $t_i$ và $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), biểu thị truy vấn thứ $i$.

Kết quả

In ra đúng $q$ dòng. Dòng thứ $i$ chứa câu trả lời cho truy vấn thứ $i$.

Nếu cỗ máy thực hiện ít hơn $t_i$ giai đoạn, hãy in ra $-1$. Ngược lại, hãy in ra kiện hàng nằm ở vị trí thứ $b_i$ tính từ bên trái sau khi đã thực hiện $t_i$ giai đoạn.

Ví dụ

Dữ liệu vào 1

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

Kết quả 1

4
2
-1
5

Giải thích 1

Cỗ máy sẽ thực hiện ba giai đoạn:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

Dữ liệu vào 2

1 1
1
1 1

Kết quả 2

-1