SPyofgame đang thực hiện một thử thách: đạt được mức Expert codeforces trong 1 tháng hoặc mất 50k. Trong lúc luyện tập, anh ấy gặp 1 bài toán như sau:

Cho mảng \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots A_N\), và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L,R\), và câu trả lời cho truy vấn là có bao nhiêu giá trị khác nhau xuất hiện đúng 2 lần trong đoạn \([L,R]\) của mảng \(A\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N, Q \leq 5*10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots A_N\) \((A_i \leq 10^9)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L,R\) \((1 \leq L \leq R \leq N)\)

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho truy vấn thứ \(i\).

Example

5 1
1 2 1 1 1
1 3 

1