Статуетки

У Боба є багато міні-фігурок, і він любить виставляти деякі з них на полиці над екраном свого комп'ютера. Боб регулярно замінює старі фігурки новими, і цей постійний процес приносить йому задоволення. Він завжди стежить за тим, щоб не виставляти одну й ту ж фігурку більше одного разу. У Боба є всього $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)~mod~n, де 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

~~~~~for~i \in [0; n - 1]

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

~~~~~вивести~x_n

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