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: 3099  Solved: 484
[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

[Submit][Status]