Cho dãy ~n~ số nguyên ~a_1, a_2, ..., a_n~ và ~m~ truy vấn. Mỗi truy vấn có dạng 2 số nguyên ~u, v~ với ý nghĩa đếm xem trong dãy con ~a_u, a_{u+1}, ..., a_v~ có bao nhiêu giá trị khác nhau mà các giá trị này xuất hiện đúng 2 lần?

Input

• Dòng đầu ghi hai số nguyên dương ~n, m (1 \leq n, m \leq 5 \times 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n (0 \leq a_i \leq 10^9)~
• ~m~ dòng cuối, mỗi dòng ghi 2 số nguyên ~u, v~ mô tả một truy vấn.

Output

• Với mỗi truy vấn in ra một dòng một số nguyên - kết quả tìm được.

Sample Input

5 1
1 2 1 1 1
1 3

Sample Output

1