Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$. Viết chương trình xử lý các truy vấn sau:

• s e: In ra số lượng cặp $(i, j)$ sao cho $s \le i < j \le e$ và $A_i > A_j$. ($1 \le s \le e \le N$)

Dữ liệu vào

Dòng đầu tiên chứa độ dài của dãy $N$ ($1 \le N \le 100{,}000$) và số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 1{,}000{,}000{,}000$)

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
2
5