시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Consider an integer sequence a1, a2, ..., an. A (strictly) increasing sequence of indices c1, c2, ..., cp, where 1 ≤ ci ≤ n, is called declining if ac1 > ac2 > ... > acp.
A sequence of indices c1, c2, ..., cp is lexicographically smaller od than a sequence of indices d1, d2, ..., dp if for some k ∈ [1,p] it holds that ci = di for each i ∈ [1,k-1] and ck < dk.
Your task is to answer several queries of the form: find the (lexicographically) k-th smallest declining sequence of indices.
The first line of the standard input contains three integers n, p and q (1 ≤ n, q ≤ 100 000, 1 ≤ p ≤ 10) that denote the length of the sequence (ai), the length of the considered declining sequences and the number of queries. The second line contains n integers ai (-109 ≤ ai ≤ 109). The following q lines contain descriptions of the queries: the j-th of these lines contains a single integer kj (1 ≤ kj ≤ 1018).
Your program should write q lines to the standard output. The j-th line should contain the kj-th smallest declining sequence of indices or a single number -1 if the requested declining sequence does not exist.
5 3 3 -1 6 5 2 1 1 5 3
2 3 4 -1 2 4 5
The declining sequences of indices of length 3 in this example are, in the lexicographical order, as follows: (2, 3, 4), (2, 3, 5), (2, 4, 5) and (3, 4, 5).
Contest > Algorithmic Engagements > PA 2011 5-1번