Problem description

W Bajtoławie organizowany jest wielki pokaz dominiarski. Polegać miał on na tym, że na wielkim stole stawiano jedną (słownie: jedną) kostkę domina, po czym zdecydowanym ruchem palca doprowadzano do jej przewrócenia. Niestety sponsor uznał, że taki plan pokazu nie spełnia jego oczekiwań. W związku z tym do pokazu postanowiono dodać jeszcze jedną kostkę, tak że ta pierwsza przewróci tą drugą. Jak się później okazało, plan po tej korekcie również nie zadowolił sponsora. W związku z tym dokonano w sumie N takich korekt¹. W każdej z nich dodano jedną (słownie: jedną) kostkę domina przed pewną inną kostkę (kostki numerujemy w kolejności, w jakiej były one dodawane). Sponsor interesuje się głównie sumarycznym czasem trwania pokazu. Można uznać, że czas przewrócenia się jednej kostki zajmuje dokładnie sekundę, oraz, że rozpoczyna ona przewracanie się kostek przed nią dopiero po swoim pełnym upadku ². Sponsor prosi Cię, abyś dla każdej korekty wyznaczył sumaryczną liczbę sekund trwania pokazu.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita N oznaczające liczbę korekt.
W następnych N liniach wejścia znajdują się opisy poszczególych korekt.
W i-tej z nich znajduje się indeks klocka stojącego za i-tym klockiem.

Wyjście

Wyjście składa się z N linii. W i-tej z nich znajduje się odpowiedź na pytanie o czas trwania pokazu po i-tej korekcie.

Ograniczenia

We wszystkich testach zachodzi zależność 1 ≤ N ≤ 10⁶
Dodatkowo w testach wartych 40% punktów zachodzi zależność 1  ≤ N ≤ 2000
Dodatkowo w testach wartych 10% punktów zachodzi zależność 1  ≤ N ≤ 10

Przykład

4
1
1
2
4

2
2
3
4