题目描述

你在一个研究 DNA 的生物信息科研小组实习。一串 DNA 上有很多不同种类的基因，被称作不同的基因类。一个基因类的基因又被一个特殊的核苷酸序列所标记，称为基因标记。一个基因类 $i$ 有两种标记，起始标记 $\texttt{s}_i$ 和结尾标记 $\texttt{e}_i$。干完一些脏活之后（培养细菌，抽取细胞，蛋白质工程等），你的科研团队成功将一段 DNA 转化成一个序列的形式，该序列只由基因标记组成。

你的科研团队提出了一个有趣的假说，认为基因的表达取决于基因类上形成的某种恰当的结构。一个基因类 $i$ 被认为是结构恰当的，就是说将序列中所有的 $\texttt{s}_i$ 和 $\texttt{e}_i$ 取出按序列中的顺序构成子序列，这个序列需是结构恰当的：

• $\texttt{s}_i\texttt{e}_i$ 是结构恰当的。
• $\texttt{s}_i N\texttt{e}_i$ 当 $N$ 是结构恰当的时，该序列是结构恰当的。
• $AB$ 当 $A,B$ 均是结构恰当的时，该序列是结构恰当的。

麻烦的是，你所研究的这种 DNA 是环状的，你需要将其从某一个位置切开后才是一个 DNA 序列，显然有的基因类是否恰当取决于你在什么位置切开它。你要解决的问题就是选择一个位置使得最大化切开后恰当的基因类数。记你切的是 $p$ 标记之前的键，那么在有多个 $p$ 满足条件时，你需要给出最小的 $p$。

输入格式

第一行输入一个正整数 $n(1\le n \le 10^6)$，表示 DNA 环的长度。

接下来一行，输入 $N$ 个基因标记，每个基因标记的输入方式是一个字符 $c(c \in { \texttt{s}, \texttt{e} })$ 和一个正整数 $i(1\le i \le 10^6)$，表示标记类型，以及该基因标记所属的基因类。

输出格式

输出两个数 $p, m$，$p$ 如题意所示，$m$ 即最大化的恰当基因类数。

样例 1

input

9
e1 e1 s1 e2 s1 s2 e42 e1 s1

output

3 1

方案如图所示。

样例 2

input

8
s1 s1 e3 e1 s3 e1 e3 s3

output

8 2

数据范围与提示

保证 $1\le n, i \le 10^6$。