P4070 [SDOI2016] Generating Spell

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.

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 $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.

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