Estás haciendo prácticas en un grupo de investigación de bioinformática que estudia el ADN. Una sola hebra de ADN consta de muchos genes, que se clasifican en distintas categorías llamadas tipos de genes. Los tipos de genes están delimitados por secuencias específicas de nucleótidos conocidas como marcadores génicos. Cada tipo de gen $i$ tiene un marcador inicial único $s_i$ y un marcador final único $e_i$. Tras muchos trabajos ingratos (cultivar bacterias, extraer células, hacer ingeniería de proteínas, etc.), tu grupo puede convertir el ADN en una forma compuesta únicamente por los marcadores génicos, eliminando todo el material genético que hay entre ellos.
Tu grupo ha propuesto la interesante hipótesis de que la interpretación de los genes depende de si los marcadores de algunos tipos de genes forman estructuras correctamente anidadas. Para decidir si los marcadores del tipo de gen $i$ forman un anidamiento correcto en una secuencia de marcadores dada $w$, hay que considerar la subsecuencia de $w$ que contiene únicamente los marcadores del tipo $i$ ($s_i$ y $e_i$), sin omitir ninguno de ellos. Las siguientes estructuras, y solo ellas, se consideran correctamente anidadas:
- $s_i e_i$
- $s_i N e_i$, donde $N$ es una estructura correctamente anidada
- $AB$, donde $A$ y $B$ son estructuras correctamente anidadas
Por tus conocimientos de informática, te han encargado investigar esta propiedad, pero hay una complicación adicional. Tu grupo estudia un tipo específico de ADN llamado ADN circular, que forma un bucle cerrado. Para estudiar el anidamiento en el ADN circular, es necesario cortar el bucle en algún punto, lo que da lugar a una secuencia única de marcadores (la dirección de lectura está fijada por las propiedades moleculares). Que un tipo de gen $i$ forme un anidamiento correcto depende ahora también del lugar donde se corte el ADN circular. Tu tarea es encontrar el punto de corte que maximice el número de tipos de genes que forman una estructura correctamente anidada. La figura D.1 muestra un ejemplo correspondiente a la entrada de ejemplo 1. El corte indicado hace que los marcadores del tipo de gen 1 estén correctamente anidados.
Figura D.1: Ilustración de la entrada de ejemplo 1 con su punto de corte óptimo.
Entrada
La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^6$), la longitud del ADN. La siguiente línea contiene la secuencia de ADN, es decir, $n$ marcadores. Cada marcador es un carácter $c$ seguido de un entero $i$, donde $c \in \{s,e\}$ indica si es un marcador inicial o final e $i$ ($1 \le i \le 10^6$) es su tipo de gen. La secuencia de ADN dada se ha obtenido cortando el ADN circular en un punto arbitrario.
Salida
Imprime una línea con dos enteros $p$ y $m$, donde $p$ es la posición de corte que maximiza el número de tipos de genes distintos que forman un anidamiento correcto y $m$ es ese número máximo. El ADN se corta justo antes del marcador número $p$ de la entrada (por ejemplo, el corte mostrado en la figura D.1 tiene $p = 3$). Si varias posiciones producen el mismo valor máximo de $m$, imprime el menor $p$ que lo haga.
Ejemplos
Entrada 1
9 e1 e1 s1 e2 s1 s2 e42 e1 s1
Salida 1
3 1
Entrada 2
8 s1 s1 e3 e1 s3 e1 e3 s3
Salida 2
8 2