P13864 P13864 [SWERC 2020] Figurines
题目背景
:::align{center}
:::
题目描述
Bob 有很多迷你手办。他喜欢在电脑屏幕上方的一个架子上展示其中的一些，并且喜欢定期更换展示的手办。这种不断变化的装饰确实令人赏心悦目。Bob 从不重复添加同一个迷你手办。Bob 只有 $N$ 个迷你手办，经过 $N$ 天后，每个手办都被添加过然后又被移除了（因此架子又空了）。
Bob 记忆力非常好。他能记住过去每一天架子上展示了哪些迷你手办。因此，Bob 想做一个小小的脑力练习，来测试自己的记忆力和计算能力。为此，Bob 用数字 $0, \dots, N-1$ 为他的手办编号，并选择一个长度为 $N$ 的整数序列 $d_0 \dots d_{N-1}$，所有整数均在范围 $[0,N]$ 内。然后，Bob 按如下方式计算序列 $x_0,\dots, x_N$：$x_0=0$，$x_{i+1}=(x_i+y_i) \bmod N$，其中 $\bmod$ 是取模运算，$y_i$ 是在第 $d_i$ 天展示的手办中，编号大于或等于 $x_i$ 的手办个数。Bob 的计算结果就是 $x_N$。
更形式化地说，如果我们用 $S(i)$ 表示第 $i$ 天架子上展示的手办对应的 $\{0,\dots,N-1\}$ 的子集，则有：
- $S(0)$ 是空集；
- $S(i)$ 是由 $S(i-1)$ 插入和移除一些元素得到的。
- 每个元素 $0 \le j < N$ 恰好被插入和移除一次，因此，最后一个集合 $S(N)$ 也是空集。
Bob 利用如下程序进行计算。
$$
\begin{array}{l}
x_0 \leftarrow 0 \\
\text{for } i \in [0;N-1] \\
\;\;\;\;\;\;\; x_{i+1} \leftarrow (x_i + \#\{y \in S(d_i) ~\text{ 满足 } ~ y \ge x_i\}) \bmod N \\
\text{output } x_N
\end{array}
$$
Bob 请你验证他的计算。为此，他将他在计算中使用的数字（$d_0, \dots, d_{N-1}$）以及他每天添加或移除了哪些手办的日志交给你。注意，一个在第 $i$ 天添加、第 $j$ 天移除的迷你手办，在满足 $i\leq k < j$ 的第 $k$ 天是存在于架子上的。你应该告诉他你在计算结束时得到的数字。
输入格式
输入由 $2N+1$ 行组成。
- 第一行包含整数 $N$。
- 第 $2$ 到第 $N+1$ 行描述了每天添加和移除的手办。
第 $i+1$ 行包含空格分隔的 $+j$ 或 $-j$，其中 $0 \le j < N$，表示 $j$ 在第 $i$ 天被添加或移除。这一行可能为空。一行中可能同时包含 $+j$ 和 $-j$，按此顺序出现。
- 第 $N+2$ 到第 $2N+1$ 行描述了序列 $d_0,\dots, d_{N-1}$。
第 $N+2+i$ 行包含整数 $d_i$，满足 $0 \le d_i \le N$。
输出格式
输出应包含一行一个整数，即 $x_N$。
说明/提示
输入 #1
```c++
3
+0 +2
-0 +1
-1 -2
1
2
2
```
输出 #1
```c++
2
```
样例解释：
输出为 $2$，因为
- 首先，$x \leftarrow 2$，因为 $S(1) = \{ 0, 2 \}$ 且 $\#\{y \in S(1) ~\text{满足}~ y \ge 0\} = 2$；
- 然后，$x \leftarrow 0$，因为 $S(2) = \{ 1, 2 \}$ 且 $\#\{y \in S(2) ~\text{满足}~ y \ge 2\} = 1$；
- 最后，$x \leftarrow 2$，因为 $S(2) = \{ 1, 2 \}$ 且 $\#\{y \in S(2) ~\text{满足}~ y \ge 0\} = 2$。
对于所有数据，保证 $N\le 10^5$。