21215번 - Figurines 출처다국어분류

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:

$x_0 \leftarrow 0$
for $i\in [0;N-1]$
    $x_{i+1} \leftarrow (x_i + \#\{y \in S(d_i) \text{ such that } y \ge x_i\}) \mod N$
output $x_N$

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$.

• $1 \le N \le 100\,000$

The output is $2$ since

• first, $x \leftarrow 2$ since $S(1) = \{ 0, 2 \}$ and $\#\{y \in S(1)  \text{ such that } y \ge 0\} = 2$;
• then, $x \leftarrow 0$ since $S(2) = \{ 1, 2 \}$ and $\#\{y \in S(2)  \text{ such that } y \ge 2\} = 1$;
• and finally, $x \leftarrow 2$ since $S(2) = \{ 1, 2 \}$ and $\#\{y \in  S(2) \text{ such that } y \ge 0\} = 2$.