Yasser's Medians

★★★★★

3.5

2 votes

Data Structures, Binary indexed tree, Datastructures, Advanced Data Structures, Fenwick (Binary Indexed) Trees

Details

Problem

Given $N$ numbers and an integer $K$ find :

$(N^{maxmed}) mod 1e9+7$

Formally: we can define $maxmed$ as the maximum median of each subarray of length $K$ .

Note that: the median of $K$ numbers indexed from $1$ is ${((K+1)/2)^{th}}$ smallest of them, rounding down for even $K$ .

Input format

The first line contains two integers $N$ and $K$ denoting the number of elements and size of the subarray.
The second line contains $N$ space-separated integers.

Output format

Print the answer as described above.

Constraints

$2 \le N,K \le 10^5$

$1 \le a_i \le 10^5$

$K \le N$

Sample Input

4 2
1 2 3 4

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the example, we can notice that we have 3 subarrays of size 2

{1,2},{2,3},{3,4} here the median of every subarray is the mean of the 2 middle values (rounded down) since we have an even size subarray.

all medians will be(1,2,3) and the $maxmed$ is 3 and finally $(N^{maxmed})$ will be $4^3 = 64$ .

Contributers:

(Nmaxmed)mod1e9+7(N^{maxmed}) mod 1e9+7