あなたは DNA を研究するバイオインフォマティクスの研究グループでインターンをしています。1本鎖の DNA は多数の遺伝子からなり、それらは遺伝子型と呼ばれる異なるカテゴリに分類されます。遺伝子型は、遺伝子マーカーと呼ばれる特定のヌクレオチド配列によって区切られます。各遺伝子型 $i$ には固有の開始マーカー $s_i$ と終了マーカー $e_i$ があります。多くの泥臭い作業（細菌の培養、細胞抽出、タンパク質工学など）を経て、研究グループはマーカー間の遺伝物質をすべて取り除き、DNA を遺伝子マーカーのみからなる形に変換できます。

研究グループは、遺伝子の解釈は一部の遺伝子型のマーカーが正しい入れ子構造を作るかどうかに依存する、という興味深い仮説を立てました。与えられたマーカー列 $w$ において遺伝子型 $i$ のマーカーが正しく入れ子になるかを判定するには、遺伝子型 $i$ のマーカー（$s_i$ と $e_i$）を1つも除かずにすべて取り出した $w$ の部分列を考える必要があります。次の構造だけが正しい入れ子構造とみなされます。

• $s_i e_i$
• $s_i N e_i$。ここで $N$ は正しい入れ子構造です。
• $AB$。ここで $A$ と $B$ は正しい入れ子構造です。

計算機に関する経験を買われ、あなたはこの性質を調べるよう任されましたが、さらに厄介な点があります。グループは環状 DNA と呼ばれる、閉じた環を形成する特殊な DNA を研究しています。環状 DNA の入れ子構造を調べるには、環をどこかで切り、マーカー列を一意に定める必要があります（読む向きは分子的な性質によって固定されています）。遺伝子型 $i$ が正しく入れ子になるかどうかは、環状 DNA を切る位置にも依存することになります。あなたの課題は、正しい入れ子構造を作る遺伝子型の数を最大にする切断位置を求めることです。図 D.1 は入力例 1 に対応する例です。図示された位置で切ると、遺伝子型 1 のマーカーが正しく入れ子になります。

図 D.1：入力例 1 とその最適な切断位置の図。

入力

入力の最初の行には DNA の長さを表す整数 $n$（$1 \le n \le 10^6$）が与えられます。次の行には DNA 配列、すなわち $n$ 個のマーカーが与えられます。各マーカーは文字 $c$ の後に整数 $i$ を続けたもので、$c \in \{s,e\}$ は開始マーカーか終了マーカーかを表し、$i$（$1 \le i \le 10^6$）はそのマーカーの遺伝子型を表します。与えられる DNA 配列は、環状 DNA を任意の位置で切って得られたものです。

出力

2つの整数 $p,m$ を1行に出力してください。$p$ は正しく入れ子になる異なる遺伝子型の数を最大にする切断位置、$m$ はその最大数です。DNA は入力の $p$ 番目のマーカーの直前で切断されます（例えば図 D.1 の切断位置では $p = 3$ です）。同じ最大値 $m$ を与える切断位置が複数ある場合、そのうち最小の $p$ を出力してください。

入出力例

入力 1

9
e1 e1 s1 e2 s1 s2 e42 e1 s1

出力 1

3 1

入力 2

8
s1 s1 e3 e1 s3 e1 e3 s3

出力 2

8 2