Ở thị trấn Thuật Toán, hai người bạn Hiếu và Đức có một bảng số gồm các giá trị nguyên dương ~A_1, A_2, \ldots, A_N~. Hai bạn này thường hay ngồi chơi trò "Thằng nào khôn hơn" để tỉ thí xem ai là người giỏi hơn, đồng thời phát triển tư duy chiến lược "game theory" để trở thành những nhà toán học tài ba. Quy tắc như sau:

• Hiếu đi trước, chọn một vị trí ~x~ trong đoạn ~[L, R]~.

• Đức đi sau, chọn một vị trí ~y~ trong đoạn ~[L, R]~.

• Gọi ~u = \min(x, y)~ và ~v = \max(x, y)~. Điểm số của lần chơi là số đoạn con liên tiếp không giảm ~[i, j]~ thỏa ~u \leq i \leq j \leq v~, tức là số cặp ~(i, j)~ sao cho ~u \leq i \leq j \leq v~ và ~A_i \leq A_{i+1} \leq \ldots \leq A_j~.

Hiếu muốn điểm số là nhỏ nhất có thể, còn Đức muốn điểm số là lớn nhất có thể, biết rằng cả hai đều chơi tối ưu. Do hai bạn trẻ của chúng ta rất hiếu chiến nên họ đấu với nhau tận ~Q~ lần, mỗi lần họ sẽ chọn ra một dãy con liên tiếp ~A_L, A_{L+1}, \ldots, A_R~ để chơi. Với mỗi lần chơi như vậy, bạn cần cho biết điểm số của trò chơi nếu cả hai đều chơi tối ưu là bao nhiêu.

Input

• Dòng đầu chứa hai số nguyên ~N, Q~ — độ dài dãy và số truy vấn.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~.

• Mỗi trong ~Q~ dòng tiếp theo chứa hai số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~, mô tả một ván chơi diễn ra trên đoạn ~A_L, A_{L+}1, \ldots, A_R~.

Output

In ra ~Q~ dòng. Dòng thứ i in một số nguyên — điểm số sau khi Hiếu và Đức cùng chơi tối ưu trên đoạn ~A_L, A_{L+}1, \ldots, A_R~.

Scoring

Sample Input 1

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

Sample Output 1

4
4
6
3

Notes

Ở truy vấn thứ nhất, nếu Hiếu chọn ~x = 2~ thì Đức sẽ chọn ~y = 4~, các dãy con không giảm sẽ là ~(4), (2), (5), (2, 5)~. Nếu Hiếu chọn ~x = 3~ thì Đức sẽ chọn ~y = 1~, các dãy con không giảm sẽ là ~(1), (4), (2), (1, 4)~. Hiếu sẽ không chọn ~x = 1~ hoặc ~x = 4~ vì các nước đi này không tối ưu.