레이팅 미적용3
Bob has a lot of mini figurines. He likes to display some of them on a shelf above his computer screen and he likes to regularly change which figurines appear. This ever-changing decoration is really enjoyable. Bob takes care of never adding the same mini figurine more than once. Bob has only \(N\) mini figurines and after \(N\) days he arrives at the point where each of the \(N\) figurines have been added and then removed from the shelf (which is thus empty).
Bob has a very good memory. He is able to remember which mini figurines were displayed on each of the past days. So Bob wants to run a little mental exercise to test its memory and computation ability. For this purpose, Bob numbers his figurines with the numbers \(0, \dots, N-1\) and selects a sequence of \(N\) integers \(d_0 \dots d_{N-1}\) all in the range \([0;N]\). Then, Bob computes a sequence \(x_0,\dots, x_N\) in the following way: \(x_0=0\) and \(x_{i+1}=(x_i+y_i)\mbox{ mod } N\) where \(\mbox{mod}\) is the modulo operation and \(y_i\) is the number of figurines displayed on day \(d_i\) that have a number higher or equal to \(x_i\). The result of Bob's computation is \(x_N\).
More formally, if we note \(S(i)\) the subset of \(\{0,\dots,N-1\}\) corresponding to figurines displayed on the shelf on day \(i\), we have:
- \(S(0)\) is the empty set;
- \(S(i)\) is obtained from \(S(i-1)\) by inserting and removing some elements.
Each element \(0 \le j < N\) is inserted and removed exactly once and thus, the last set \(S(N)\) is also the empty set. The computation that Bob performs corresponds to the following program: flushleft \(x_0 \leftarrow 0\)
for \(i\in [0;N-1]\)
$x_{i+1} \leftarrow (x_i + #{y \in S(d_i) ~\mbox{such that} ~ y \ge
x_i}) \mod N$
output \(x_N\) flushleft
Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the \(d_0, \dots, d_{N-1}\)) as well as the log of which figurines he added or removed every day. Note that a mini figurine added on day \(i\) and removed on day \(j\) is present on a day \(k\) when \(i\leq k < j\). You should tell him the number that you found at the end of the computation.
The input is composed of \(2N+1\) lines.
- The first line contains the integer \(N\).
- Lines \(2\) to \(N+1\) describe the figurines added and removed. Line \(i+1\) contains space-separated +\(j\) or -\(j\), with \(0 \le j < N\), to indicate that \(j\) is added or removed on day \(i\). This line may be empty. A line may contain both +\(j\) and -\(j\), in that order.
- Lines \(N+2\) to \(2N+1\) describe the sequence \(d_0,\dots, d_{N-1}\). Line \(N+2+i\) contains the integer \(d_i\) with \(0 \le d_i \le N\).
The output should contain a single line with a single integer which is \(x_N\).
3
+0 +2
-0 +1
-1 -2
1
2
2
2