선물

문제

연구를 열심히 하는 민용이에게 친절한 교수님은 길이가 $N$인 수열을 선물로 주셨다. 그리고 교수님은 민용이가 해결해야 하는 $Q$개의 과제도 주셨다. 각 과제는 다음과 같은 형태다.

• l r: 수열의 $l$번째 원소부터 $r$번째 원소까지의 원소로만 이루어진 부분 수열에서 등장 횟수가 정확히 두 번인 서로 다른 수의 개수를 출력한다.

민용이는 이게 무슨 선물이냐며 여러분에게 과제 해결을 맡겼다. 민용이를 위해 교수님의 과제를 해결하는 프로그램을 작성해 보자.

입력

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. ($1\le N, Q\le 500\,000$)

둘째 줄에는 수열의 각 원소를 의미하는 $N$개의 정수가 공백으로 구분되어 주어진다. 각 원소는 $1\,000\,000\,000$보다 작은 자연수다.

셋째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 교수님의 과제가 l r의 형태로 주어진다. ($1\le l\le r\le N$)

출력

교수님의 과제에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

5 1
1 2 1 1 1
1 3

예제 출력 1

1

예제 입력 2

5 2
1 1 1 1 1
2 4
2 3

예제 출력 2

0
1

예제 입력 3

5 2
1 1 2 2 3
1 1
1 5

예제 출력 3

0
2