Статуетки

У Боба є багато міні-фігурок, і він любить виставляти деякі з них на полиці над екраном свого комп'ютера. Боб регулярно замінює старі фігурки новими, і цей постійний процес приносить йому задоволення. Він завжди стежить за тим, щоб не виставляти одну й ту ж фігурку більше одного разу. У Боба є всього $n$ міні-фігурок, і через $n$ днів він досягає моменту, коли кожна з $n$ фігурок була додана, а потім прибрана з полиці, залишаючи її порожньою.

Боб має чудову пам'ять і може запам'ятати, які міні-фігурки були виставлені в кожен з минулих днів. Тому він вирішив провести невелику розумову вправу, щоб перевірити свою пам'ять і обчислювальні здібності. Для цього він нумерує свої фігурки числами від $0$ до $n-1$ і обирає послідовність $n$ цілих чисел $d_0,...,d_{n-1}$ в діапазоні $[0;n]$. Потім він обчислює послідовність $x_0,...,x_n$ наступним чином: $x_0=0$, а $x_{i+1}=(x_i+y_i)modn$, де mod — це операція за модулем, а $y_i$ — це кількість фігурок, виставлених у день $d_i$, номер яких більший або дорівнює $x_i$. Результатом обчислень Боба є $x_n$.

Більш формально, якщо $S(i)$ — це підмножина $\{0,...,n-1\}$, що відповідає фігуркам, виставленим на полиці в $i$-ий день, то:

• $S(0)$ — порожня множина;

• $S(i)$ отримується з $S(i-1)$ шляхом вставки і видалення деяких елементів.

Кожен елемент $j(0\le j<n)$ вставляється і видаляється рівно один раз, тому остання множина $S(n)$ також є порожньою. Обчислення, яке виконує Боб, відповідає наступній програмі:

$x_0=0$

$fori\in [0;n-1]$

$x_{i+1}=(x_i+\#\{y\in S(d_i)такещоy\ge x_i\})modn$

$вивестиx_n$

Боб просить вас перевірити його розрахунки. Для цього він надає вам числа, які він використовував при обчисленні $(d_0,...,d_{n-1})$, а також журнал того, які фігурки він додавав або видаляв кожен день. Зверніть увагу, що міні-фігурка, додана в день $i$ і прибрана в день $j$, присутня в день $k(i\le k<j)$. Ви повинні повідомити йому число, яке знайдете в кінці обчислень.

Вхідні дані

Складається з $2\cdot n+1$ рядків.

• Перший рядок містить ціле число $n(1\le n\le 10^5)$.

• Рядки від $2$ до $n+1$ описують додані і видалені фігурки. Рядок $i+1$ містить розділені пробілами $+j$ або $-j$, $0\le j<n$, щоб вказати, що $j$ додається або видаляється в день $i$. Цей рядок може бути порожнім. Рядок може містити як $+j$, так і $-j$ саме в цьому порядку.

• Рядки з $n+2$ по $2\cdot n+1$ описують послідовність $d_0,...,d_{n-1}$. Рядок $n+2+i$ містить ціле число $d_i(0\le d_i\le n)$.

Вихідні дані

Виведіть одне число $x_n$.

Приклади