레이팅 미적용설명
5 \(s / 512\) \(MB / 140\) points
어린 Mirko는 아주 단순한 사람이다. Mirko의 친구 Darko는 그에게 자연수 \(N\)
개로 이루어진 배열을 주고, Mirko가 답해야 하는 배열에 대한 질의 \(Q\)
개를 던졌다.
각 질의는 두 정수, 즉 배열에서 어떤 구간의 왼쪽 끝과 오른쪽 끝의 위치로 이루어진다. 질의의 답은 주어진 구간에 정확히 두 번 나타나는 서로 다른 값의 개수이다.
제약
총 56점에 해당하는 테스트 케이스에서는 수 \(N\)
과 \(Q\)
가 5000보다 크지 않다.
입력 형식
입력의 첫째 줄에 정수 \(N\)
과 \(Q\)
(1 ≤ N, Q
≤ 500 000
)이 주어진다.
입력의 둘째 줄에 1 000 000 000보다 작은 자연수 \(N\)
개가 주어진다. 배열의 원소이다.
다음 \(Q\)
개의 줄에는 문제에서 말한 두 정수 \(L\)
과 R (
1 ≤ \(L\)
≤ \(R\)
≤ \(N\)
)이 주어진다.
출력 형식
출력은 \(Q\)
개의 줄로 이루어져야 하며, 각 줄에 해당 질의의 답을 차례로 출력한다.
예제 1
입력
5 1
1 2 1 1 1
1 3
5 2
1 1 1 1 1
2 4
2 3
5 2
1 1 2 2 3
1 1
1 5출력
output
output
1
0
1
0
2설명
Clarification of the first test case:
In the interval from the first to the third element, there is only one number (number 1) that appears
exactly twice.
문제 정보