An có một dãy số và muốn biết vị trí đầu tiên (nhỏ nhất) xuất hiện giá trị nhỏ nhất trong một đoạn \([l, r]\).

Nói cách khác, tìm chỉ số \(i\) nhỏ nhất sao cho \(l \le i \le r\) và \(a_i\) là giá trị nhỏ nhất trong đoạn \([l, r]\).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra vị trí đầu tiên tìm được.

Ví dụ

Input:

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

Output:

2
5
3