Let's denote the keys already pressed as ~a_1, \dots, a_N~. We define an array of numbers ~b_1, \dots, b_N~ in the following way:

$$\displaystyle b_i = \begin{cases} 0 & \text{if }i = 1 \\ b_{i-1}+1 & \text{if }i > 1, a_i > a_{i-1} \\ b_{i-1}-1 & \text{if }i > 1, a_i < a_{i-1} \\ b_{i-1} & \text{if }i > 1, a_i = a_{i-1} \end{cases}$$

Let's denote the partial sum of array ~b~ as ~p_i~. It is easy to see that the ~i^\text{th}~ note that Mirka will press is exactly ~p_i \times K + a_1~.

If Mirka plays the ~i^\text{th}~ note of the song, it holds ~p_i \times K + a_1 = a_i~. If ~p_i = 0~, then the accuracy of the ~i^\text{th}~ note does not depend on ~K~ at all, otherwise it will be played correctly if ~K~ is equal to ~(a_i-a_1)/p_i~ (notice that the quotient must be a non-negative integer).

Therefore, for each note for which ~p_i \ne 0~ there exists at most one good candidate for ~K~. All the candidates can be put in an array and then we can sort them, find the one with the most appearances and choose that one as the optimum.

The complexity of the solution is ~\mathcal O(N \log N)~ because of the sorting.