18800번 - 도로 공사

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 ≤ K ≤ N ≤ 100,000​​​​, 1 ≤ Q ≤ 100,000)

둘째 줄에는 도로의 상태를 나타내는 길이 N의 수열 A가 주어진다. (-10⁹​ ≤ A_i ≤ 10⁹)

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

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