1827 . Yet another simple task ^____^

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

93.3% (56/60)

Submission's AC Ratio

38.8% (150/387)

Tags

Description

given a sequence B=B0,B1,…,BN−1
for each query (P,K), find the minimum S
s.t. there are at least K entries in B that satisfies

  • |P−i|≤S
  • Bi≤S

where Bi denotes the ith entry of B

Input Format

The first line contains two integers N,M.
The second line contains N integers separated with spaces. This is the sequence B.
The following M lines are M queries and each query is consists of two integers P,K.

Output Format

For each query, you should output one integer denoting your answer.

Sample Input 1

10 2
1 2 3 2 10 2 3 3 3 2
1 3
3 3

Sample Output 1

2
2

Hints

1≤N≤105
1≤M≤105
1≤Bi≤N
0≤P<N
1≤K≤N

Problem Source

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 131072 262144 1
1 2500 131072 262144 2
2 2500 131072 262144 3
3 2500 131072 262144 4
4 2500 131072 262144 5
5 2500 131072 262144 6
Submit
Back to Top