Yuto và Platina chuẩn bị chơi một trò chơi có tên là Trò chơi Mảng con Không giảm. Trò chơi được thực hiện trên một mảng $A$ có độ dài $N$.

Yuto chọn một số nguyên trước, sau đó Platina chọn một số nguyên. Các số được chọn bởi người chơi phải nằm trong khoảng từ $L$ đến $R$ (bao gồm cả hai đầu mút). Gọi hai số nguyên được chọn là $a$ và $b$, được sắp xếp sao cho $a \le b$. Khi đó, điểm số đạt được trong trò chơi là số lượng các cặp $(i, j)$ sao cho $a \le i \le j \le b$ và đoạn $[i, j]$ tạo thành một mảng con không giảm trong mảng $A$.

Chúng ta nói rằng $[i, j]$ tạo thành một mảng con không giảm khi với mọi $x$ và $y$ thỏa mãn $i \le x \le y \le j$, điều kiện $A[x] \le A[y]$ luôn đúng.

Yuto muốn tối thiểu hóa điểm số, trong khi Platina muốn tối đa hóa điểm số đó. Trò chơi này rất thú vị nên chúng ta sẽ chơi nó $T$ lần. Tất cả các ván chơi đều sử dụng cùng một mảng $A$, nhưng các ván chơi khác nhau có thể sử dụng các giá trị $L$ và $R$ khác nhau.

Giả sử cả hai người chơi đều chơi một cách tối ưu, hãy tìm số điểm mà họ sẽ đạt được trong mỗi ván chơi.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $T$ ($1 \le N, T \le 500\,000$): độ dài của mảng và số lượng ván chơi.

Dòng thứ hai chứa các giá trị của mảng $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$).

Mỗi dòng trong $T$ dòng tiếp theo mô tả một ván chơi bằng hai số nguyên dương $L_i$ và $R_i$ ($1 \le L_i \le R_i \le N$): các giá trị $L$ và $R$ được sử dụng cho ván chơi đó.

Dữ liệu ra

Với mỗi ván chơi, in ra điểm số của ván đó trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

8 5
7 10 3 1 9 5 5 2
1 5
2 2
5 8
1 8
3 5

Dữ liệu ra 1

4
1
4
7
3