Generating Spells

A spell string consists of many spell characters, which can be represented by numbers. For example, the spell characters 1 and 2 can be concatenated to form the spell string $[1, 2]$.

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

For example, when $S = [1, 2, 1]$, its generated spells are $[1]$, $[2]$, $[1, 2]$, $[2, 1]$, and $[1, 2, 1]$, totaling five types. When $S = [1, 1, 1]$, its generated spells are $[1]$, $[1, 1]$, and $[1, 1, 1]$, totaling three types.

Initially, $S$ is an empty string. There are $n$ operations in total, where each operation appends a spell character to the end of $S$. After each operation, you need to determine the total number of distinct generated spells of the current spell string $S$.

Input

The first line contains an integer $n$. The second line contains $n$ integers, where the $i$-th integer represents the spell character added in the $i$-th operation.

Output

Output $n$ lines, each containing one number. The number on the $i$-th line represents the number of distinct generated spells of $S$ after the $i$-th operation.

Examples

Input 1

7
1 2 3 3 3 1 2

Output 1

1
3
6
9
12
17
22

Constraints

For 10% of the data, $1 \le n \le 10$. For 30% of the data, $1 \le n \le 100$. For 60% of the data, $1 \le n \le 1000$. For 100% of the data, $1 \le n \le 100000$.

The numbers $x$ used to represent spell characters satisfy $1 \le x \le 10^9$.