12031203 SUSTech Online Judge
Problem 1203 --Nth Element in Sliding Window [Hard I]

1203: Nth Element in Sliding Window [Hard I]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1520  Solved: 223
[Submit][Status][Web Board]

Description

Given a sequence \(a_1, a_2,\cdots, a_m\), there is a sliding window of size \(k\) from the very left of the sequence to the very right. You can only see the \(k\) numbers in the window. Each time the sliding window moves right by one position. 

For each time there is an integer \(n_i\), you are asked the \(n_i\)-th element in the window. The k-th element indicates that the element will be in the k-th position after sorting in ascending order.

Input

The first line contains two integers \(m\) and \(k\), \((1 \le m \le 10^5,1\le k\le m)\)

The second line contains m distinct integers separated by space \(a_i\)\((-2147483648\le a_i \le 2147483647)\).

The next line contains \(m-k+1\) integers separated by space \(n_i\)\((1\le n_i\le k)\)

Output

Output \(m-k+1\) lines, each line contain a number represented the answer to each window

Sample Input

6 3
201 91 29 13 11 -5
3 1 2 1

Sample Output

201
13
13
-5

HINT

Balanced binary search tree

Source

[Submit][Status]