도로 공사

SciOI시의 시장인 상렬이는 새로운 도로를 건설하려고 한다. 하지만 상렬이가 도로를 지으려는 땅이 너무 울퉁불퉁해서, 땅을 다지는 작업만 몇 년이 걸릴 것으로 예상된다. 도로를 지을 땅은 직선 형태이며, 높이가 같거나 다른 $N$개의 조각으로 나뉘어 있다. 도로의 높이는 음수일 수도 있다. 도로의 상태는 각 도로 조각의 높이를 나타내는 길이 $N$의 수열 $A$로 표현된다.

다행히 마법사인 상렬이는 연속한 $K$개 조각의 높이를 같은 값만큼 높이거나 낮추는 마법을 쓸 수 있다. 이때 $K$는 고정되어 있다.

예를 들어 $N = 5$이고 $K = 2$이며 도로의 상태가 다음과 같다고 하자.

3 5 6 2 9

상렬이가 세 번째와 네 번째 조각의 높이를 2만큼 높이는 마법을 쓰면 도로의 상태는 다음과 같이 바뀐다.

3 5 8 4 9

또한 상렬이의 마법은 도로의 경계를 벗어나서도 쓸 수 있으며, 범위를 넘어간 부분의 마법은 무시된다. 예를 들어 $K = 3$일 때 경계를 벗어나 0번째, 첫 번째, 두 번째 조각에 마법을 쓰는 것이 가능하다. 이때 0번째 조각에 대한 마법은 무시되어, 첫 번째와 두 번째 조각에만 마법을 쓰는 것이 된다.

상렬이는 도로를 정확히 어디에 지을지 아직 정하지 못했지만, 주어진 도로의 어떤 연속된 구간에 짓게 될 것은 확실하다. 구간에 도로를 짓게 된다면, 마법을 써서 그 구간에 속한 도로 조각들의 높이를 모두 같게 만들어야 한다. 그러나 마법을 너무 많이 쓰면 주변에 마법사라는 사실이 들킬 수 있으므로, 상렬이는 최소한의 횟수로 마법을 쓰고자 한다.

상렬이가 생각하는 도로를 지을 구간 후보는 총 $Q$개이다. 각 후보에 대해 상렬이가 최소로 써야 하는 마법의 수를 구하는 프로그램을 작성하여라. 모든 쿼리는 독립적이다.

첫 줄에는 $N$, $K$, 그리고 도로를 건설할 구간의 후보 수 $Q$가 주어진다. ($1 \le K \le N \le 100{,}000$, $1 \le Q \le 100{,}000$)

둘째 줄에는 도로의 상태를 나타내는 길이 $N$의 수열 $A$가 주어진다. ($-10^9 \le A_i \le 10^9$)

셋째 줄부터 $Q$개의 줄에는 도로를 건설할 구간의 후보가 각각 주어진다. $i$번째 후보는 두 정수 $l_i$, $r_i$로 표현되며, 도로의 $l_i$번째 조각부터 $r_i$번째 조각까지로 이루어진 구간임을 의미한다. ($1 \le l_i \le r_i \le N$)

$Q$개의 줄에, 각 도로 구간 후보에서 상렬이가 최소로 사용해야 하는 마법의 수를 한 줄에 하나씩 출력한다. 마법으로 도로 조각들의 높이를 원하는 대로 만들 수 없다면, $-1$을 출력한다.