26270번 - 최빈값과 쿼리

문제

크기가 $N$인 정수 수열 $A$와 상수 $K$가 주어진다. 다음과 같은 쿼리 $Q$개가 주어질 때, 각 쿼리에 대한 답을 출력하라.

• $l$ $r$: $A$의 $l$번째 원소부터 $r$번째 원소까지 이외의 다른 원소를 포함하지 않는 부분수열 중, 같은 수가 $K$번 이상 등장하는 연속된 부분 수열의 최소 길이를 출력한다. 단, 이런 부분 수열이 존재하지 않을 경우 $-1$을 출력한다.

입력

첫 번째 줄에 $N,ドル $K,ドル $Q$가 순서대로 주어진다. (1ドル \le N, K, Q \le 200,000円$)

두 번째 줄에 수열 $A$의 원소 $N$개가 순서대로 주어진다. (1ドル \le A_i \le N$)

세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 $l,ドル $r$이 주어진다. (1ドル \le l \le r \le N$)

출력

$Q$개의 줄에 걸쳐 각 줄마다 쿼리에 대한 답을 순서대로 출력한다.

제한

노트

$B$가 $A$의 연속된 부분수열이라는 것은 1ドル\le j\le M$인 모든 정수 $j$에 대해 $B$의 $j$번째 원소와 $A$의 $i+j-1$번째 원소가 동일한 1ドル$ 이상 $N$이하의 정수 $M$과 1ドル\le i+M<N$인 정수 $i$가 존재한다는 것이다.