Cho ~N~ cây cột, trong đó cột thứ ~i~ có độ cao là ~h[i]~.

Có một chú ếch xanh tên là ~Nếch~, chú luôn ước mơ được nhảy vút lên chạm tới bầu trời cao rộng. Vì vậy, mỗi khi đứng trên những cây cột, ~Nếch~ chỉ chọn nhảy tới cây cột gần nhất có chiều cao lớn hơn nơi chú đang đứng. Tuy nhiên, cuộc sống không bao giờ dễ dàng như những ước mơ của ~Nếch~. Leo lên càng cao thì té xuống càng đau, nhưng điều quan trọng nhất là sau mỗi lần vấp ngã, liệu ~Nếch~ có đủ sức mạnh để tự mình đứng dậy và tiếp tục hành trình hay không...

Chú ý, nếu có ~2~ cột cao hơn cột hiện tại và xa như nhau thì ~Nếch~ sẽ chọn cột cao hơn.

Với ~Q~ truy vấn, cho ~x~ là vị trí xuất phát và ~k~ là số lần nhảy tối đa. Hãy tính độ cao lớn nhất mà ~Nếch~ có thể đạt được.

Đầu vào

Dòng đầu gồm 2 số nguyên ~N~ và ~Q~ là số lượng cột và số truy vấn ~(1 \le Q \le N \le 10^5)~.

Dòng thứ hai ghi ~N~ số nguyên dương là độ cao các cột của dãy ~h~, độ cao mỗi cột không quá ~10^9~.

~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x~ và ~k~ là vị trí xuất phát và số lần nhảy tối đa ~(1 \le x, k \le N)~.

Đầu ra

Gồm ~Q~ dòng, mỗi dòng là độ cao tối đa mà ~Nếch~ có thể đạt được.

Ví dụ

Đầu vào

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

Đầu ra

3
4
5
5
5