In meteorology, a common statistical tool is the median of a given set of measurements. (You can find a definition of the median in the Notes section.)
You are writing software for a device that measures temperature once a second. The device has a small digital display. At any moment, the display has to show the median of temperatures measured in the last K seconds.
Before you upload your software into the device, you would like to test it on a computer.
Instead of measuring temperatures, we will use a random number generator (RNG) to generate fake temperatures. Given three ints seed, mul and add, we define a sequence of temperatures:
In addition to the parameters of the RNG, you will be given two ints N and K.
Consider the sequence containing the first N temperatures generated by the RNG (i.e., values t0 to tN-1). This sequence has N-K+1 contiguous subsequences of length K. For each such subsequence compute its median.
Your method will be given the numbers seed, mul, add, N, and K. Compute all the medians as described above, and return a long containing their sum.
|-||Given K numbers, their median is the ((K+1)/2)-th smallest of them, rounding down for even K, and indexing from 1.|
For example, the median of (1, 2, 6, 5, 4, 3) is 3, and the median of (11, 13, 12, 14, 15) is 13.
|-||seed, mul, and add are between 0 and 65535, inclusive.|
|-||N is between 1 and 250,000, inclusive.|
|-||K is between 1 and 5,000, inclusive.|
|-||N is greater than or equal to K.|