It is a difficult task to directly answer what the maximal possible average is, so let's instead try to answer the question of whether the maximal possible average is larger than or equal to some value ~P~. If we succeed in this, then we can solve the task using binary search over ~P~.

This task also seems difficult, but let's notice this: if we subtract ~X~ from every number in the array, then the average of all subsequences is reduced by exactly ~X~. Now we can subtract ~P~ from all the numbers in the array and see if a subsequence exists with an average larger than or equal to ~0~. This task is simpler because it is equivalent to the question of whether a subsequence exists with the sum larger than or equal to zero.

If we calculate the prefix sum ~S~ of the input array, then the sum of a subsequence ~[a, b]~ is equal to ~S[b]-S[a-1]~. For every possible ~b~, we can ask ourselves whether such ~a~ exists that ~S[b]-S[a-1] \ge 0~, or ~S[b] \ge S[a-1]~. Also, we mustn't forget the condition for the minimal subsequence length, ~b-a+1 \ge K~ or ~a \le b+1-K~.

Iterating over boundary value ~b~ from left to right, we can store the minimal value ~S[a-1]~ seen so far in a special variable and check if it meets the requirement for the current ~b~. If it does, we have found a subsequence with an average larger than or equal to ~P~.

Each time we increment variable ~b~ by ~1~, exactly one new value comes into consideration for ~a~ and it is ~a = b-K+1~. By doing so, we check if ~S[b-K]~ is smaller than the current minimal value and update it if it is.