CF1486D.Max Median

You are a given an array $a$ of length $n$. Find a subarray $a[l..r]$ with length at least $k$ with the largest median.

A median in an array of length $n$ is an element which occupies position number $\lfloor \frac{n + 1}{2} \rfloor$ after we sort the elements in non-decreasing order. For example: $median([1, 2, 3, 4]) = 2$, $median([3, 2, 1]) = 2$, $median([2, 1, 2, 1]) = 1$.

Subarray $a[l..r]$ is a contiguous part of the array $a$, i. e. the array $a_l,a_{l+1},\ldots,a_r$ for some $1 \leq l \leq r \leq n$, its length is $r - l + 1$.

给定一个长度为 $n$ 的数组 $a$。请找出一个长度至少为 $k$ 的子数组 $a[l..r]$，使其中位数最大。

一个长度为 $n$ 的数组的中位数，是指将该数组所有元素按非递减顺序排序后，位于位置 $\lfloor \frac{n + 1}{2} \rfloor$ 上的元素。例如：
$median([1, 2, 3, 4]) = 2$，
$median([3, 2, 1]) = 2$，
$median([2, 1, 2, 1]) = 1$。

子数组 $a[l..r]$ 是数组 $a$ 的一个连续片段，即对某个满足 $1 \leq l \leq r \leq n$ 的下标范围，取 $a_l, a_{l+1}, \ldots, a_r$ 构成的数组，其长度为 $r - l + 1$。

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

Output one integer $m$ — the maximum median you can get.

输出一个整数 $m$ —— 你能得到的最大中位数。

In the first example all the possible subarrays are $[1..3]$, $[1..4]$, $[1..5]$, $[2..4]$, $[2..5]$ and $[3..5]$ and the median for all of them is $2$, so the maximum possible median is $2$ too.

In the second example $median([3..4]) = 3$.

在第一个例子中，所有可能的子数组为 $[1..3]$、$[1..4]$、$[1..5]$、$[2..4]$、$[2..5]$ 和 $[3..5]$，它们的中位数均为 $2$，因此可能的最大中位数也是 $2$。

在第二个例子中，$median([3..4]) = 3$。