Bài đăng

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$.

Dữ liệu vào

• 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,\dots ,A_N$ $(1\le A_1,A_2,\dots ,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.

Dữ liệu ra

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

Ràng buộc

• $1\le N,Q\le 3\times {10}^5$.
• $1\le A_i\le {10}^9$.
• $1\le U\le V\le N$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $N,Q\le 50$.
• Subtask 2 ($15\%$ số điểm): $N\le 500$.
• Subtask 3 ($10\%$ số điểm): $N\le 5000$.
• Subtask 4 ($20\%$ số điểm): $Q=1$; $U=1$; $V=N$.
• Subtask 5 ($20\%$ số điểm): $Q\le 30000$.
• Subtask 6 ($20\%$ số điểm): Không có ràng buộc nào thêm.

Ví dụ