Cho dãy số nguyên gồm ~n~ phần tử ~a_1, a_2, …, a_n~ và ~Q~ truy vấn. Mỗi truy vấn có dạng một cặp số nguyên ~u, v~. Với mỗi truy vấn ~u, v~, bạn cần trả lời câu hỏi số nhỏ nhất trong các số từ số thứ ~u~ tới số thứ ~v~ là bao nhiêu?

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, …, a_n~;
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~.

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Giới hạn:

• ~1 ≤ n ≤ 10^6; 1 ≤ u ≤ v ≤ n; 1 ≤ Q ≤ 10^5; |a_i| ≤ 10^9~.

Output

• Ghi trên một dòng ~Q~ số nguyên, mỗi số là câu trả lời cho một truy vấn (theo đúng thứ tự), hai số liên tiếp cách nhau một dấu cách.

Sample

Input #1

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

Output #1

-1 3 -3

Problem source: Chuyên Sơn La Online Judge