AlgoLiga 2018

Jasio ma N klocków ułożonych w ciągu i ponumerowanych od 1 do N. Z tych klocków będzie układał wieże składające się z k klocków. Zastanawia się, jaka będzie różnica w wysokości między najwyższą a najniższą wieżą, jaką jest w stanie ułożyć z klocków, od tego z numerem a do tego o numerze b w ciągu włącznie.

Wejście:

W pierwszej linii trzy liczby: N - liczba klocków , k - liczba klocków w budowanych wieżach, Q - liczba zapytań. 3 < N ≤ 300000, 0 < k ≤ min(N,10), Q ≤ 200000

W następnej linii N liczb: h₁, h₂, h₃, ..., h_n - wysokości poszczególnych klocków  0 < h < 10⁹

W następnych Q liniach dwie liczby a b (1 ≤ a, b ≤ N;  a+k-1 ≤ b)

Wyjście:

Należy w kolejnych liniach wypisać Q liczb, które są odpowiedziami na pytanie: jaką maksymalną różnicę wysokości da się osiągnąć dla poszczególnych przedziałów?

Przykład:

Wejście:
5 2 3
3 4 1 6 2
1 2
1 4
3 5

Wyjście:
0
6
5