Alice là kỹ sư phát triển nền tảng mạng xã hội VOI giúp cho cộng đồng lập trình viên tương tác với nhau. Có ~N~ bài đăng được đánh số từ ~1~ đến ~N~ theo trình tự thời gian đăng bài. Alice phân loại các bài đăng theo chủ đề, bài đăng thứ ~i~ ~(1 \le i \le N)~ có chủ đề là ~A_i~.

Alice định nghĩa một đoạn ~[L, R]~ gồm các bài đăng liên tiếp từ chỉ số ~L~ đến chỉ số ~R~ ~(1 \le L \le R \le N)~ là toàn vẹn nếu với mỗi chủ đề ~t~, hoặc không có bài nào có chủ đề ~t~ nằm trong đoạn ~[L, R]~ hoặc tất cả các bài có chủ đề ~t~ đều nằm trong đoạn này.

Yêu cầu: Vào dịp Noel, Alice công bố dữ liệu chủ đề của ~N~ bài đăng và mở cuộc thi trên VOI cho các lập trình viên tham gia. Alice lần lượt đưa ra ~Q~ truy vấn, mỗi truy vấn cho biết một cặp số nguyên ~U, V~ ~(1 \le U \le V \le N)~ và yêu cầu thí sinh đếm số đoạn ~[L, R]~ là toàn vẹn với ~U \le L \le R \le V~.

Cụ thể, với mỗi truy vấn, cần đếm xem có bao nhiêu cặp ~L, R~ thỏa mãn:

• ~U \le L \le R \le V~;

• Không tồn tại hai giá trị ~i, j~ nào sao cho:

  • ~(1 \le i < L)~ hoặc ~(R < i \le N)~;

  • ~L \le j \le R~;

  • ~A_i = A_j~.

Input

Vào từ file văn bản POST.INP:

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_1, A_2, \ldots, A_N \le 10^9)~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~U~ và ~V~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản POST.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số là đáp án cho truy vấn tương ứng.

Scoring

Sample Input 1

7 2
1 2 2 3 1 6 3
1 7
2 6

Sample Output 1

3
2

Notes

• Truy vấn 1, có 3 đoạn toàn vẹn:

$$[1,7], [2,3], [6,6]$$

• Truy vấn 2, có 2 đoạn toàn vẹn:

$$[2,3], [6,6]$$