Cho dãy \(a_1,a_2,…,a_n\), gọi \(f(i,j)\) là số nguyên không âm nhỏ nhất không xuất hiện \(a_i,a_{i+1},…,a_j\).

Yêu cầu: Cho \(q\) truy vấn, mỗi truy vấn gồm hai số \((l,r)\) hãy tính \(∑_(l≤i≤j≤r)f(i,j)\)

Input

• Dòng đầu tiên chứa \(n,q (1≤n,q≤2×10^5 ).\)

• Dòng thứ hai chứa \(n\) số \(a_i (0≤a_i≤n).\)

• \(q\) dòng tiếp theo mỗi dòng chứa hai số \(l,r (1≤l≤r≤n)\) tương ứng với các truy vấn.

Output

• Ứng với truy vấn đưa ra trên một dòng.

Ràng buộc

• Subtask 1: 15%: \(q≤200,r-l≤200\)

• Subtask 2: 15%: \(n≤5000\)

• Subtask 3: 15%: dãy \(a_i\) là hoán vị từ 0 đến \(n-1\)

• Subtask 4: 15%: \(a_i≤100\) và không có hai truy vấn \((l,r)\) và \((l',r')\) mà \(l<l'\) và \(r'<r\)

• Subtask 5: 20%: \(l=1\)

• Subtask 6: 20%: không có ràng buộc gì thêm.

Sample Input

6 3
0 1 3 0 1 2
1 2
1 6
3 5

Sample Output

3
34
6