Você faz um estágio em um grupo de pesquisa em bioinformática que estuda DNA. Uma única fita de DNA consiste em muitos genes, divididos em diferentes categorias chamadas tipos de genes. Os tipos de genes são delimitados por sequências específicas de nucleotídeos conhecidas como marcadores gênicos. Cada tipo de gene $i$ possui um marcador inicial único $s_i$ e um marcador final único $e_i$. Após muitos trabalhos ingratos (cultivo de bactérias, extração de células, engenharia de proteínas e assim por diante), seu grupo consegue converter o DNA em uma forma composta apenas pelos marcadores gênicos, removendo todo o material genético entre os marcadores.
Seu grupo propôs a interessante hipótese de que a interpretação dos genes depende de os marcadores de alguns tipos de genes formarem estruturas corretamente aninhadas. Para decidir se os marcadores do tipo de gene $i$ formam um aninhamento correto em uma sequência de marcadores $w$, é preciso considerar a subsequência de $w$ que contém apenas os marcadores do tipo $i$ ($s_i$ e $e_i$), sem deixar nenhum deles de fora. As seguintes estruturas, e somente elas, são consideradas corretamente aninhadas:
- $s_i e_i$
- $s_i N e_i$, em que $N$ é uma estrutura corretamente aninhada
- $AB$, em que $A$ e $B$ são estruturas corretamente aninhadas
Por causa de seus conhecimentos de computação, você foi encarregado de investigar essa propriedade, mas há mais uma complicação. Seu grupo estuda um tipo específico de DNA chamado DNA circular, que forma uma alça fechada. Para estudar o aninhamento no DNA circular, é necessário cortar a alça em algum ponto, obtendo uma sequência única de marcadores (o sentido de leitura é fixado pelas propriedades moleculares). Se um tipo de gene $i$ forma um aninhamento correto agora também depende de onde o DNA circular é cortado. Sua tarefa é encontrar o ponto de corte que maximize o número de tipos de genes que formam uma estrutura corretamente aninhada. A Figura D.1 mostra um exemplo correspondente à entrada de exemplo 1. O corte indicado faz com que os marcadores do tipo de gene 1 fiquem corretamente aninhados.
Figura D.1: Ilustração da entrada de exemplo 1 com seu ponto de corte ótimo.
Entrada
A primeira linha da entrada contém um inteiro $n$ ($1 \le n \le 10^6$), o comprimento do DNA. A linha seguinte contém a sequência de DNA, isto é, $n$ marcadores. Cada marcador é um caractere $c$ seguido de um inteiro $i$, em que $c \in \{s,e\}$ indica se é um marcador inicial ou final e $i$ ($1 \le i \le 10^6$) é o tipo de gene do marcador. A sequência de DNA fornecida foi obtida cortando o DNA circular em um ponto arbitrário.
Saída
Imprima uma linha com dois inteiros $p$ e $m$, em que $p$ é a posição de corte que maximiza o número de tipos de genes distintos que formam um aninhamento correto, e $m$ é esse número máximo. O DNA é cortado imediatamente antes do marcador de número $p$ da entrada (por exemplo, o corte da Figura D.1 tem $p = 3$). Se mais de uma posição de corte produzir o mesmo valor máximo de $m$, imprima o menor $p$ que o faça.
Exemplos
Entrada 1
9 e1 e1 s1 e2 s1 s2 e42 e1 s1
Saída 1
3 1
Entrada 2
8 s1 s1 e3 e1 s3 e1 e3 s3
Saída 2
8 2