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 ⌊n+12⌋ 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
Correct answer will be upvoted else downvoted. Computer science.
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 ⌊n+12⌋ 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 al,al+1,…,ar for some 1≤l≤r≤n, its length is r−l+1.
Input
The first line contains two integers n and k (1≤k≤n≤2⋅105).
The second line contains n integers a1,a2,…,an (1≤
Output
Output one integer m — the maximum median you can get.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 1 images
