Description

A spell string consists of many spell characters, and a spell character can be represented by a number. For example, we can piece together spell characters $1,2$ to form a spell string $[1,2]$.

A non-empty substring of a spell string $S$ is called a generating spell of $S$.

For example, when $S = [1,2,1]$, its generating spells are $[1],[2],[1,2],[2,1],[1,2,1]$, five in total. When $S = [1,1,1]$, its generating spells are $[1],[1,1],[1,1,1]$, three in total. Initially, $S$ is an empty string.

There are $n$ operations in total. In each operation, one spell character is appended to the end of $S$. After each operation, you need to determine how many distinct generating spells the current spell string $S$ has.

Input Format

The first line contains an integer $n$.

The second line contains $n$ numbers. The $i$-th number denotes the spell character $x_i$ appended in the $i$-th operation.

Output Format

Output $n$ lines, one number per line.
The number on the $i$-th line denotes the number of distinct generating spells after the $i$-th operation.

7
1 2 3 3 3 1 2

1
3
6
9
12
17
22

Hint

Constraints
For 10% of the testdata, it is guaranteed that $1 \le n \le 10$.
For 30% of the testdata, it is guaranteed that $1 \le n \le 100$.
For 60% of the testdata, it is guaranteed that $1 \le n \le 10^3$.
For 100% of the testdata, it is guaranteed that $1 \le n \le 10^5$, $1 \leq x_i \leq 10^9$.

Translated by ChatGPT 5