A naive simulation does not meet the execution time limit because the song switches at most \(O(T)\) times, so we use the periodicity.

Let \(S = A_1 + \dots + A_N\). \(S\) seconds after the playlist starts, song \(1\) starts to play again. Thus, if \(T_0 \geq S\), we can see that the answer for \(T = T_0\) and \(T = T_0 - S\) are the same. By applying this fact repeatedly, we can always boil down to \(T \lt S\) by considering the remainder when \(T\) is divided by \(S\).

If \(T \lt S\), there is at most \(N-1\) switches of songs in a naive simulation. Therefore, this problem has been solved in a total of \(O(N)\) time.

Sample code (C++)