CF 174

A: each operation, update sum and remember extra at the last element. When pop, add extra[last] to extra[last-1]. B: notice that we only have (pos, hop) states, where pos = 1 to n, hop = 0 or 1, meaning whether next is x + a[x] or x - a[x]. We can assume we start at pos > 1, because (x, y) is (1, 0) to begin with and the first move is necessarily pos=1 and hop = 0, after that since a[1] = 1 to n-1, so next pos must be greater than 1. So the start state is some (pos, hop=1) with pos >= 2. And it is not hard to see that if we ever have the same (pos, hop) appearing again, then it is a loop. Otherwise either we end at some (pos, hop) and next move get to pos out of bounds, that is, pos > n or pos <= 0. This will stop the sequence. The only remaining case is when pos = 1. Then if hop = 1, we know that next move is x - a[x], where we have x = 1 and a[1] >= 1, so next move must have pos <= 0, and the sequence will stop. The other case is that hop = 0, then we have next move is x + a[x] for x = 1. This will get us to next pos = 1 + a[1]. However, the only way we can get to this pos = 1 + a[1] is by starting at (x, y) = (1, 0) and when a[1] is set to the number such that pos = 1 + a[1], so we started at x=1 and val = a[1], and after some steps we are at x=1 again, and the next pos must be 1 + a[1], so we must have a loop (**this part is not clear as I would like to**). We have covered all cases and it is clear that we only need to do dfs for n*2 states, the graph has 2n nodes and 2n edges, given n = 10^5, it runs in time limit.