Since the constraint states \(N \le 200000\), the solution of naively simulating the movements of the robot takes \(\Theta(N^2)\) does not finish in time limit and it will get TLE. Let’s call a sequence of movements “move in the positive direction by \(A_1\). Move in the positive direction by \(A_2\). Move in the positive direction by \(A_3\). \(\ddots\) Move in the positive direction by \(A_2\).” as “Movement \(i\)”. Here, for all integer \(i\) such that \(1 \le i \le N\), the following values can easily found in a total of \(O(N)\) time (in the increasing order of \(i\)):

• \(p_i\) : The overall delta of coordinate performed by movement \(i\)
• \(q_i\) : The maximum coordinate that robot reaches if it starts movement \(i\) from coordinate \(0\)

With those values calculated, the answer can also be found as follows:

• Let \(r = 0\), which stores the answer (maximum coordinate)
• Let \(x = 0\), which stores the current coordinate, and perform the following operations for each \(i = 1, 2, 3, \dots , N\):
  • Replace \(r\) with \(\max(r, x + q_i)\)
  • Replace \(x\) with \(x + p_i\)

The total time complexity is \(O(N)\).