Du machst ein Praktikum in einer bioinformatischen Forschungsgruppe, die DNA untersucht. Ein einzelner DNA-Strang besteht aus vielen Genen, die in verschiedene Kategorien, sogenannte Gentypen, unterteilt sind. Gentypen werden durch bestimmte Nukleotidsequenzen abgegrenzt, die als Genmarker bezeichnet werden. Jeder Gentyp $i$ hat einen eindeutigen Startmarker $s_i$ und einen eindeutigen Endmarker $e_i$. Nach viel schmutziger Arbeit (Bakterienzüchtung, Zellextraktion, Protein-Engineering und so weiter) kann deine Forschungsgruppe DNA in eine Form umwandeln, die nur aus den Genmarkern besteht, und dabei sämtliches genetische Material zwischen den Markern entfernen.
Deine Forschungsgruppe hat die interessante Hypothese aufgestellt, dass die Interpretation von Genen davon abhängt, ob die Marker einiger Gentypen korrekt verschachtelte Strukturen bilden. Um festzustellen, ob die Marker des Gentyps $i$ in einer gegebenen Markerfolge $w$ korrekt verschachtelt sind, betrachtet man die Teilfolge von $w$, die ausschließlich die Marker des Gentyps $i$ ($s_i$ und $e_i$) enthält, ohne einen davon auszulassen. Die folgenden und nur die folgenden Strukturen gelten als korrekt verschachtelt:
- $s_i e_i$
- $s_i N e_i$, wobei $N$ eine korrekt verschachtelte Struktur ist
- $AB$, wobei $A$ und $B$ korrekt verschachtelte Strukturen sind
Aufgrund deiner Informatikkenntnisse wurdest du mit der Untersuchung dieser Eigenschaft beauftragt, doch es gibt eine weitere Schwierigkeit. Deine Gruppe untersucht einen besonderen DNA-Typ namens zirkuläre DNA, also DNA, die einen geschlossenen Ring bildet. Um die Verschachtelung darin zu untersuchen, muss man den Ring an einer Stelle aufschneiden; dadurch entsteht eine eindeutige Markerfolge (die Leserichtung ist durch molekulare Eigenschaften festgelegt). Ob ein Gentyp $i$ korrekt verschachtelt ist, hängt nun auch davon ab, wo die zirkuläre DNA aufgeschnitten wird. Deine Aufgabe ist es, die Schnittstelle zu finden, die die Anzahl der Gentypen mit korrekt verschachtelter Struktur maximiert. Abbildung D.1 zeigt ein Beispiel zur Beispieleingabe 1. Beim eingezeichneten Schnitt sind die Marker des Gentyps 1 korrekt verschachtelt.
Abbildung D.1: Darstellung der Beispieleingabe 1 mit ihrer optimalen Schnittstelle.
Eingabe
Die erste Eingabezeile enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$), die Länge der DNA. Die nächste Zeile enthält die DNA-Sequenz, also $n$ Marker. Jeder Marker ist ein Zeichen $c$, gefolgt von einer ganzen Zahl $i$, wobei $c \in \{s,e\}$ angibt, ob es sich um einen Start- oder Endmarker handelt, und $i$ ($1 \le i \le 10^6$) der Gentyp des Markers ist. Die gegebene DNA-Sequenz wurde durch Aufschneiden der zirkulären DNA an einer beliebigen Stelle gewonnen.
Ausgabe
Gib eine Zeile mit zwei ganzen Zahlen $p$ und $m$ aus. Dabei ist $p$ die Schnittposition, welche die Anzahl verschiedener korrekt verschachtelter Gentypen maximiert, und $m$ diese maximale Anzahl. Die DNA wird unmittelbar vor dem $p$-ten Eingabemarker aufgeschnitten (zum Beispiel gilt für den Schnitt in Abbildung D.1 $p = 3$). Falls mehrere Schnittpositionen denselben Maximalwert von $m$ liefern, gib das kleinste solche $p$ aus.
Beispiele
Eingabe 1
9 e1 e1 s1 e2 s1 s2 e42 e1 s1
Ausgabe 1
3 1
Eingabe 2
8 s1 s1 e3 e1 s3 e1 e3 s3
Ausgabe 2
8 2