Ca khúc Tuổi Đá Buồn được ra đời trong những năm tháng cố nhạc sỹ Trịnh Công Sơn dạy học ở Bảo Lộc. Ông sống trong một căn phòng nhỏ, có ô cửa sổ nhìn ra con đường dốc quanh co trước nhà. Chính từ ô cửa sổ này, Trịnh Công Sơn đã ngồi nhìn những cơn mưa trút xuống, những đám mây mù phủ kín lối đi và viết nên những ca khúc để đời, trong đó có bài hát "Tuổi Đá Buồn".

Là một người yêu nhạc Trịnh, Dũng Phan vừa ngồi đắm mình trong giai điệu, vừa nhớ Hà Lan. Dũng đăm chiêu nhìn ra mặt đường đầy sỏi đá phía trước hiên nhà. Chợt anh nhận ra trên con đường nhà mình cũng có \(N\) viên đá lớn có kích thước to nhỏ khác nhau. Các viên đá nằm thẳng hàng, được đánh số theo thứ tự từ \(1\) đến \(N\). Dũng từ từ đứng dậy, vẫn say đắm trong âm nhạc, chậm rãi bước đến vô thức nhặt lên một hòn đá. Biết rằng hòn đá đó nằm trong đoạn \([L,\ R]\), và vì Dũng luôn thích số \(2\) nên sẽ nhặt hòn đá có kích thước lớn thứ hai trong đoạn. Hãy cho biết hòn đá Dũng nhặt có thứ tự bao nhiêu?

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(N, Q\) - lần lượt là số lượng viên đá và số truy vấn;
• Dòng thứ hai chứa \(N\) số nguyên dương \(w_1,\ w_2,\ldots,\ w_n\ (w_i\neq w_j,\ \forall i\neq j)\) thể hiện kích thước của từng viên đá;
• Tiếp theo là \(Q\) dòng, mỗi dòng gồm hai số nguyên dương \(L,\ R\ (L<R)\) thể hiện một truy vấn. Cần in ra chỉ số của hòn đá có kích thước lớn thứ nhì trong đoạn \([L,\ R]\).

Output

• Mỗi câu trả lời cho một truy vấn được in ra trên một dòng, gồm một số nguyên duy nhất.

Ví dụ

Sample input

5 3
4 2 7 6 9
1 3
2 5
3 4

Sample output

1
3
4

Ràng buộc

• Có \(40\%\) test tương ứng với \(40\%\) số điểm của bài có \(1\leq N,\ Q\leq10^3\);
• Có \(60\%\) test khác tương ứng với \(60\%\) số điểm của bài có \(10^3<N,\ Q\leq10^5\);
• \(1\leq w_i\leq 10^9\);
• \(1\leq L<R\leq N\).