Background

The problem setter one minute later stopped the problem setter at this moment from writing an interesting background story.

(The background image comes from Phigros artwork. If there is any infringement, please inform the problem setter.)

Problem Description

You are given a string $S$, where $S=\overline{s_1s_2\dots s_n}$.

There is a string $T$, initially $T=S$. You may perform several operations. In each operation, you can choose a substring of $S$ and insert it into any position of $T$.

You want, after some operations, to make $T=\overline{s_1s_1s_2s_2\dots s_ns_n}$. Define $f(S)$ as the minimum number of operations needed to satisfy this condition.

In addition, the string $S$ will undergo some changes. Specifically, there are $q$ modification operations. Each modification gives $p$ and $\texttt{c}$, meaning set $s_p\gets \texttt{c}$. Here $\texttt{c}$ means any lowercase letter, not the character whose ASCII code is $99$.

You need to output the value of $f(S)$ at the beginning and after each modification.

Input Format

The first line contains an integer $q$, the number of modifications.
The second line contains a string $S$ consisting only of lowercase letters.
The next $q$ lines each contain an integer $p$ and a lowercase letter $\texttt{c}$, representing one modification.

Output Format

There are $q+1$ lines. Each line contains an integer, the answer.

2
aabc
2 b
4 b

2
2
1

Hint

Idea: cyffff, Solution: cyffff, Code: cyffff, Data: cyffff

Clock Paradox - WyvernP (Insane12.6)

The input/output files of this problem are large. Please use appropriate I/O methods.

Hint

A string $A$ is a substring of string $S$ if and only if there exist $1\le l\le r\le |S|$ such that $A=\overline{s_ls_{l+1}\dots s_{r}}$.

Sample Explanation

Before all modifications, $f(S)$ is computed as follows:

Initially, $S=T=\texttt{aabc}$.

In the first operation, choose the substring $\texttt{aa}$ of $S$ and insert it at the very beginning of $T$. After the operation, $T=\texttt{aaaabc}$.

In the second operation, choose the substring $\texttt{bc}$ of $S$ and insert it after the $5$-th character of $T$. After the operation, $T=\texttt{aaaabbcc}$, which meets the requirement.

After the first and second modifications, $S$ becomes $\texttt{abbc}$ and $\texttt{abbb}$ respectively. After these two modifications, $f(S)$ is $2$ and $1$ respectively.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le|S|\le3\times10^6$, $0\le q\le 3\times10^6$. It is guaranteed that $S$ consists only of lowercase letters, and $\texttt{c}$ is a single lowercase letter.

Translated by ChatGPT 5