Mode and Queries

You are given an integer sequence $A$ of length $N$ and a constant $K$. For each of the $Q$ queries below, print the answer.

• $l$ $r$: Among the contiguous subsequences that use only the elements $A_l, A_{l+1}, \ldots, A_r$, output the minimum length of one in which some value appears at least $K$ times. If no such subsequence exists, output $-1$.

The first line contains $N$, $K$, and $Q$ in this order. ($1 \le N, K, Q \le 200\,000$)

The second line contains the $N$ elements of $A$ in order. ($1 \le A_i \le N$)

Each of the next $Q$ lines contains $l$ and $r$. ($1 \le l \le r \le N$)

Print $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

A sequence $B$ is a contiguous subsequence of $A$ if there exist an integer $M$ with $1 \le M \le N$ and an integer $i$ with $1 \le i+M < N$ such that the $j$-th element of $B$ equals the $(i+j-1)$-th element of $A$ for every integer $j$ with $1 \le j \le M$.