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 một bài toán.

Cho mảng \(A\) gồm \(N\) phần tử, phần tử thứ \(i\) có giá trị \(A[i]\). Có \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L\) và \(R\). Câu trả lời cho truy vấn này là có bao nhiêu giá trị khác nhau xuất hiện chính xác 2 lần trong đoạn \([L;R]\) đó

Input

• Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N,Q \leq 500 000)\)
• Dòng thứ hai là các số nguyên \(A[i]\) \((A[i] \leq 1 000 000 000)\)
• \(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

• Gồm Q dòng, mỗi dòng là câu trả lời của từng truy vấn

Example

5 1
1 2 1 1 1
1 3

1