시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 18 7 7 53.846%

문제

오늘은 BOJ캠프 마지막날. 여러분들은 민호의 소원을 들어줘야 한다.

민호의 소원은 간단하다. 민호가 가지고 길이 N의 수열에서 민호가 x, y라고 말하면 x부터 y까지의 구간에 세번 이상 등장하는 수의 개수를 대답해 주는 것이다.

세번 이상 등장하는 수의 등장 횟수를 출력하는 것이 아니라 세번 이상 등장하는 수의 종류의 개수를 대답해야 하는것에 유의해야 한다.

예를 들어 [x, y]가 [1, 3, 3, 3, 3, 2, 2, 2, 7, 1, 7] 이라면 2라고 대답해야 하는 것이다.

민호의 소원들 들어주자.

입력

첫 번째 줄에 N, Q ( 1 ≤ N, Q ≤ 100,000 ) 이 공백을 구분으로 주어진다. 이는 민호가 가지고 있는 수열의 길이와 민호가 여러분에게 말할 소원의 개수이다.

두 번째 줄에 N개의 수 Ai ( 1 ≤ Ai ≤ 100,000, 1 ≤ i ≤ N ) 이 공백을 구분으로 차례대로 주어진다.

서 번째 줄부터 Q개의 줄에 걸쳐 x, y ( 1 ≤ x ≤ y ≤ N ) 이 공백을 구분으로 주어진다.

출력

Q개의 줄에 걸쳐 민호의 소원에 대한 여러분들의 답을 차례대로 출력한다.

예제 입력 1

9 7
3 2 3 1 3 1 2 1 1
3 7
1 7
8 9
3 7
1 3
2 4
1 8

예제 출력 1

0
1
0
0
0
0
2