题目描述

农民约翰的$\red{N}$头牛（$\red{1<=N<=100000}$）站在沿途的不同位置一维长栅栏。

第$\red{i}$头奶牛站在位置$\red{x_i}$（范围为$\red{0...}$$\red{1000000000}$的整数）并且已经繁殖了($\red{b_i}$对于格恩西岛或"$\red{H}$"代表荷斯坦）。

没有两头奶牛占据同一位置。

$\red{FJ}$要为县城拍连续间隔的奶牛照片 公平，但我们希望他的所有品种都能在照片中得到公平的体现。

因此，他希望确保，对于存在于 照片，每个品种的数量相同（例如，一张带有 所有荷斯坦牛都可以，与 $\red{27 }$只荷斯坦牛和 $\red{27 }$根西岛的合影还可以，但是 与 $\red{10 }$只荷斯坦和 $\red{9 }$只根西岛合影不合适）。

帮助$\red{FJ}$参加他的公平 通过找到满足 $\red{FJ }$的 照片的最大尺寸来拍摄照片 约束。

照片的大小最大和最大之间的差异 照片中奶牛的最小位置。

$\red{FJ}$有可能 最终只拍了一头牛的照片，在这种情况下，这张照片会 大小为零。

输入格式

第$\red{1}$行：整数$\red{N.}$

第$\red{2...}$$\red{1+N}$行：$\red{i+1}$行包含$\red{x_i}$和$\red{b_i}$。

输出格式

第$\red{1}$行：一个整数，表示展会的最大规模照片

样例

输入样例

6
4 G
10 H
7 G
16 G
1 G
3 H

输出样例

7

提示

输入详细信息： 有六头奶牛的品种（从左到右）为$\red{G}$、$\red{H}$、$\red{G}$、$\red{G}$、$\red{H}$、$\red{G}$。

样本输出 $\red{7}$个输出细节：农民约翰能拍到的最大的$\red{fair photo}$是中间$\red{4}$头奶牛，其中包括$\red{2}$头霍尔斯泰牛和$\red{2}$头根西岛牛。