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\)
4 2 1 2 3 4
64
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\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor