Poklon

미르코는 아주 단순한 사람이다. 미르코의 친구 다르코가 자연수 $N$개로 이루어진 배열을 주고, 이 배열에 관한 질문 $Q$개를 던졌다. 미르코는 질문에 모두 답해야 한다.

각 질문은 두 정수로 이루어지며, 두 정수는 배열의 한 구간의 왼쪽 끝과 오른쪽 끝 위치이다. 질문의 답은 주어진 구간에 정확히 두 번 등장하는 서로 다른 값의 개수이다.

첫째 줄에 정수 $N$과 $Q$가 주어진다. ($1 \le N, Q \le 500\,000$)

둘째 줄에 배열의 원소인 $N$개의 자연수가 주어진다. 각 수는 $1\,000\,000\,000$보다 작다.

다음 $Q$개의 줄에는 각각 질문을 나타내는 두 정수 $L$과 $R$이 주어진다. ($1 \le L \le R \le N$)

$Q$개의 줄에 걸쳐, 입력으로 주어진 순서대로 각 질문의 답을 한 줄에 하나씩 출력한다.

첫 번째 예제에서 첫 번째 원소부터 세 번째 원소까지의 구간에 정확히 두 번 등장하는 수는 1 하나뿐이다.