민호의 소원

민호가 길이 $N$의 수열 $A_1, A_2, \dots, A_N$을 하나 가지고 있다. 민호는 두 정수 $x$, $y$를 말하면서 구간 $[x, y]$에 세 번 이상 등장하는 수가 몇 종류인지 물어본다.

등장 횟수의 합이 아니라 세 번 이상 등장하는 수의 종류 개수를 답해야 한다. 예를 들어 구간에 놓인 수가 $1, 3, 3, 3, 3, 2, 2, 2, 7, 1, 7$이면 $3$이 네 번, $2$가 세 번 등장하므로 답은 $2$다.

민호의 소원 $Q$개에 모두 답하자.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다 ($1 \le N, Q \le 100\,000$). 각각 민호가 가진 수열의 길이와 민호가 말할 소원의 개수다.

둘째 줄에 수열의 원소 $A_i$가 순서대로 공백으로 구분되어 주어진다 ($1 \le A_i \le 100\,000$, $1 \le i \le N$).

셋째 줄부터 $Q$개의 줄에 각 소원의 $x$와 $y$가 공백으로 구분되어 주어진다 ($1 \le x \le y \le N$).

$Q$개의 줄에 각 소원의 답을 입력에 주어진 순서대로 출력한다.