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 ≤ i ≤ 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 ≤ L ≤ R ≤ 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ở một cuộc thi trên VOI cho cộng đồng lập trình viên. 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 ≤ U ≤ V ≤ N)~ và yêu cầu thí sinh đếm số đoạn ~[L, R]~ toàn vẹn với ~U ≤ L ≤ R ≤ V~.

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

• ~U ≤ L ≤ R ≤ V~;
• Không tồn tại hai giá trị ~i, j~ nào sao cho:
  • ~(1 ≤ i < L)~ hoặc ~(R < i ≤ N)~;
  • ~L ≤ j ≤ 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 ≤ N, Q ≤ 3 × 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ (~1 ≤ A_1, A_2, ..., A_N ≤ 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.

Sample Input

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

Sample Output

3
2

• 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]~.

Subtasks