Question
The Oracle’s Sliding Wisdom
In the ancient kingdom of Eldoria, the royal oracle studies sequences of magical energy levels to predict the future.
You are given an array of n integers representing the energy levels of magical crystals arranged in a line. The oracle examines every contiguous subarray (window) of size k.
For each window, the oracle computes its median value:
- If k is odd, the median is the middle element after sorting the window.
- If k is even, the median is the smaller of the two middle elements after sorting the window.
Your task is to calculate the sum of medians of all subarrays of size k.
Input
The first line contains two integers n and k — the size of the array and the window size.
The second line contains n integers — a1, a2, ..., an representing the energy levels of the crystals.
Output
Print a single integer — the sum of medians of all contiguous subarrays of size k.
Example
Example 1:
Input:
Subarrays of size 3 are:
[1, 3, 2] → median = 2
[3, 2, 6] → median = 3
[2, 6, 4] → median = 4
Total = 2 + 3 + 4 = 9.
Input:
5 3
1 3 2 6 49Subarrays of size 3 are:
[1, 3, 2] → median = 2
[3, 2, 6] → median = 3
[2, 6, 4] → median = 4
Total = 2 + 3 + 4 = 9.