Counting Distinct Magic Substrings

A magic string is a sequence of magic characters, where each magic character is represented by an integer. For example, the magic string [1,2] is formed by concatenating the magic characters 1 and 2.

For any magic string \(S\), a nonempty contiguous substring of \(S\) is called a generated magic of \(S\). For example, if \(S=[1,2,1]\), then its generated magics are:

\[ [1],\; [2],\; [1,2],\; [2,1],\; [1,2,1] \]

Note that repeated substrings are counted only once. For instance, when \(S=[1,1,1]\) the generated magics are \([1], [1,1], [1,1,1]\).

Initially, \(S\) is an empty string. You will be given \(n\) operations. In each operation, a magic character is appended to the end of \(S\). After each operation, output the current number of distinct generated magics of \(S\) (i.e. the number of distinct nonempty substrings).

The answer must be computed exactly (without modular arithmetic).

inputFormat

The first line contains a single integer \(n\) \((1 \leq n \leq 10^5)\), the number of operations.

The second line contains \(n\) integers, each representing a magic character that is appended to \(S\). Each magic character is an integer in the range \(1 \leq c \leq 10^9\).

outputFormat

Output \(n\) lines. The \(i\)th line should contain the number of distinct nonempty substrings (generated magics) of the magic string \(S\) after the \(i\)th operation.

sample

3
1 2 1

1
3
5

</p>