E - 図書館の貸出管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は大きな図書館の司書をしています。図書館には N 冊の本が書架に一列に並んでおり、左から順に本 1, 本 2, \ldots, 本 N と番号が付けられています。

現在、すべての本は貸出中で書架にはありません。本 i（1 \leq i \leq N）の返却予定日は日付 D_i です。本 i は日付 D_i に返却されて書架に戻り、それ以降ずっと書架に置かれたままになります。すなわち、日付 T において本 i が書架にある条件は D_i \leq T です。

高橋君は利用者から Q 件の問い合わせを受け付けます。j 件目（1 \leq j \leq Q）の問い合わせでは、日付 T_j と本の番号の区間 [L_j, R_j]（両端を含む）が指定されます。高橋君は、区間 [L_j, R_j] 内の本のうち日付 T_j の時点で書架にある本の冊数を調べます。すなわち、L_j \leq i \leq R_j かつ D_i \leq T_j を満たす本 i の個数を c_j とします。

ただし、図書館の貸出カートには最大 K 冊までしか載せられません。c_j \leq K であればまとめて貸し出すことができますが、c_j > K の場合はカートに載りきらないためリクエストを処理できません。

各問い合わせについて、c_j \leq K ならば c_j を、c_j > K ならば -1 を出力してください。

なお、各問い合わせは互いに独立です。ある問い合わせで本が貸し出されることはなく、書架にある本の状態はどの問い合わせに対しても同一です。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq N
  • 1 \leq Q \leq 10^5
  • 1 \leq D_i \leq 10^9 （1 \leq i \leq N）
  • 1 \leq L_j \leq R_j \leq N （1 \leq j \leq Q）
  • 1 \leq T_j \leq 10^9 （1 \leq j \leq Q）
  • 入力はすべて整数である。

入力

N K Q
D_1 D_2 \ldots D_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • 1 行目には、本の冊数を表す整数 N、貸出カートに載せられる最大冊数を表す整数 K、問い合わせ数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各本の返却予定日を表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
  • 3 行目から Q 行にわたり、各問い合わせの情報が与えられる。
  • 2 + j 行目（1 \leq j \leq Q）では、j 件目の問い合わせにおける区間の左端 L_j、右端 R_j、問い合わせの日付 T_j が、スペース区切りで与えられる。

出力

Q 行で出力せよ。j 行目（1 \leq j \leq Q）には、j 件目の問い合わせに対する答えを出力せよ。すなわち、区間 [L_j, R_j] 内で D_i \leq T_j を満たす本の冊数 c_j が K 以下であれば c_j を、K を超えていれば -1 を出力せよ。

入力例 1

5 3 3
3 1 4 1 5
1 5 2
2 4 4
1 3 3

出力例 1

2
3
2

入力例 2

5 2 3
3 1 4 1 5
1 5 4
1 2 3
3 5 1

出力例 2

-1
2
1

入力例 3

10 3 5
5 2 8 1 3 7 4 6 9 10
1 10 5
3 7 4
1 5 2
2 8 7
6 10 10

出力例 3

-1
3
2
-1
-1

入力例 4

20 5 8
15 3 20 7 12 1 18 9 4 11 6 14 2 17 8 19 5 10 16 13
1 20 10
1 10 5
5 15 12
11 20 15
1 5 3
8 14 9
3 18 7
1 20 20

出力例 4

-1
3
-1
-1
1
4
-1
-1

入力例 5

1 1 1
1000000000
1 1 1000000000

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi works as a librarian at a large library. The library has N books arranged in a row on a bookshelf, numbered Book 1, Book 2, \ldots, Book N from left to right.

Currently, all books are checked out and none are on the bookshelf. The scheduled return date for Book i (1 \leq i \leq N) is day D_i. Book i is returned and placed back on the shelf on day D_i, and remains on the shelf from that point onward. That is, Book i is on the shelf on day T if and only if D_i \leq T.

Takahashi receives Q queries from library patrons. The j-th query (1 \leq j \leq Q) specifies a day T_j and a range of book numbers [L_j, R_j] (inclusive on both ends). Takahashi needs to determine the number of books within the range [L_j, R_j] that are on the shelf as of day T_j. Specifically, let c_j be the number of books i satisfying L_j \leq i \leq R_j and D_i \leq T_j.

However, the library's lending cart can hold at most K books. If c_j \leq K, all the books can be loaded onto the cart and lent out, but if c_j > K, the request cannot be processed because the books won't fit on the cart.

For each query, output c_j if c_j \leq K, or -1 if c_j > K.

Note that each query is independent of the others. No books are actually checked out as a result of any query, and the state of books on the shelf is the same for every query.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq N
  • 1 \leq Q \leq 10^5
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Input

N K Q
D_1 D_2 \ldots D_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • The first line contains three space-separated integers: N representing the number of books, K representing the maximum number of books the lending cart can hold, and Q representing the number of queries.
  • The second line contains space-separated integers D_1, D_2, \ldots, D_N representing the scheduled return date of each book.
  • The following Q lines contain the information for each query.
  • The (2 + j)-th line (1 \leq j \leq Q) contains three space-separated values: the left endpoint L_j, the right endpoint R_j, and the query date T_j for the j-th query.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to the j-th query. Specifically, if the number of books c_j in the range [L_j, R_j] satisfying D_i \leq T_j is at most K, output c_j; if it exceeds K, output -1.

Sample Input 1

5 3 3
3 1 4 1 5
1 5 2
2 4 4
1 3 3

Sample Output 1

2
3
2

Sample Input 2

5 2 3
3 1 4 1 5
1 5 4
1 2 3
3 5 1

Sample Output 2

-1
2
1

Sample Input 3

10 3 5
5 2 8 1 3 7 4 6 9 10
1 10 5
3 7 4
1 5 2
2 8 7
6 10 10

Sample Output 3

-1
3
2
-1
-1

Sample Input 4

20 5 8
15 3 20 7 12 1 18 9 4 11 6 14 2 17 8 19 5 10 16 13
1 20 10
1 10 5
5 15 12
11 20 15
1 5 3
8 14 9
3 18 7
1 20 20

Sample Output 4

-1
3
-1
-1
1
4
-1
-1

Sample Input 5

1 1 1
1000000000
1 1 1000000000

Sample Output 5

1