#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Following the robbery of the IOI trio, the Squidzofrenzic Calamari have received an e-mail from the National Organisation of Illegal Activities and Whatever not (NOI -- the rest is not acronimised), stating that its president Eel Nya R.B. wants to inspect the success of the distribution of iPads among the file and rank of the ranks of the Squidzofrenzic Calamari.

Not wanting to be seen as a fiasco, the president of the Committee of Squidzofrenzic Calamari has decided to present as best a picture of the standard of living of his city as possible.

This would be easy, having already arranged for Eel Nya R.B. to visit the Museum of Achievements, which documents the achievements (dubious ones included of course) of squids in every possible aspect over the past 100,000 years of squidgy murky history, the Kafe Hotel, a 42-star hotel located right in the center of the prime district of town, as well as the house belonging to none other than the president of the Committee of Squidzofrenzic Calamari himself.

However, possibly to make life difficult, Eel Nya R.B. has already demanded that he gets shown around a part of the heartlands of the city, to get a feel of the realities of living in the community of Squidzofrenzic Calamari.

Also, Eel Nya R.B. had already made it clear that the quality of life in a society is determined by the median quality of life of its constituents.

Furthermore, the president of the Committee of Squidzofrenzic Calamari believes strongly that the only indicator of quality of life happens to be the quantity of iPads a squid possesses.

To make matters worse, Eel Nya R.B. is a busy eel, and demands that in his visit to the land of the Squidzofrenzic Calamari, he is only shown a consecutive length of the biggest residential estate in town, which fortunately for you, happens to be a linear estate consisting of *N* houses. The number of iPads in the *i*-th house will be *P_i*.

Can you save the president of the Committee of Squidzofrenzic Calamari from embarrassment and from a row of houses, each with iPads in them, choose *M* consecutive houses such that the median number of iPads is maximised?

## Input

The first line of the input will contain two integers *N* and *M* (1 ≤ *M* ≤ *N* ≤ 1,000,000). *M* will always be an odd integer.

The second line of the input will contain *N* integers, with the *i*-th integer representing *P_i*. To simplify matters for you, the *N* integers will be a permutation of the set of integers {1,2,...,*N*}.

## Output

The first line of the output will contain one integer, representing the best median which can be obtained.

## Sample Input 1

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

## Sample Output 1

7

## Explanation for Sample Output 1

By picking the sequence of houses [9 2 6 8 7], the median will be 7, which is the optimal.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 20 | 2s | 32MB | Average |

2 | 0 | 0 | 2s | 32MB | Average |

### Judge Compile Command

g++-8 ans.cpp -o inspection -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512