408137: GYM102994 B Gifted Composer

Acesrc is a gifted composer. He likes writing tuneful and melodic songs. Every song he writes can be viewed as a sequence of musical notes, and each musical note represents the pitch and the duration of the sound. In this problem, we consider only the following seven primary pitches

Acesrc composes a song in the following way. Initially, the sequence of notes is empty. Every day, he inserts a new note at the beginning or at the end of the sequence, until the song is done.

Acesrc particularly likes songs with repetitions. For a song with $$$n$$$ musical notes, we say the song has a repetition of length $$$k$$$ $$$(1 \leq k \leq n)$$$, if the song can be partitioned into one or more identical sections with $$$k$$$ notes, optionally followed by an incomplete section, which is an initial part of a complete section. For example, do re do re do can be partitioned into do re | do re | do, so it has a repetition of length 2; similarly, do re mi do re mi has a repetition of length 3, and do re do re mi has a repetition of length 5.

Acesrc wants to know, after he adds a note each day, the number of different lengths of repetitions the song has. Can you help him?

The first line of input consists of a single line $$$n$$$ $$$(1 \leq n \leq 10^6)$$$, the number of days Acesrc uses to compose the song. The $$$i$$$th of the remaining $$$n$$$ lines contains a character $$$a$$$ $$$(a \in \{\texttt{p}, \texttt{a}\})$$$ (where p denotes prepend, i.e., inserting at the beginning, and a denotes append, i.e., inserting at the end) and a string $$$s$$$ $$$(s \in \{\texttt{do}, \texttt{re}, \texttt{mi}, \texttt{fa}, \texttt{sol}, \texttt{la}, \texttt{si}\})$$$, representing the action Acesrc takes in the $$$i$$$th day.

Output $$$n$$$ lines. The $$$i$$$th line should be a single integer, denoting the answer for the $$$i$$$th day.

5
a do
p re
a re
a do
p do

1
1
2
2
3

5
a re
a do
a re
p do
a mi

1
1
2
2
1