题目描述

有 N 头奶牛站在一条数轴上，第 $i$ 头奶牛的位置是 $P_i$ ，奶牛不会重叠站在同一个位置，第 i 头奶牛的颜色是 $C_i$ ，其中 $C_i$ 要么是字符 ‘G’ 要么是字符 ‘H’ 。现在农夫 FJ 想给一段连续的奶牛照一张相，前提是满足一下三个条件之一：

1. 这连续一段奶牛的颜色全部是 ‘G’ 。

2. 这连续一段奶牛的颜色全部是 ‘H’ 。

3. 这连续一段奶牛，颜色是 ‘H’ 的奶牛数量和颜色是 ‘G’ 的奶牛数量相等。

FJ 要求照出来的相尽可能的宽，不妨设相片中最右边奶牛位置是 $P_j$, 相片中最左边奶牛位置是 $P_i$ ，那么 FJ 要使得 $P_j-P_i$ 最大。如果照片只有一头奶牛，那么输出 0 。

输入格式

第一行，一个整数 N ( 1 <= N <= 100000 )。

接下来有 N 行，每行的格式是： $P_i$、$C_i$ 。( 0 <= $P_i$、$C_i$ <= 1,000,000,000 )

输出格式

一个整数，输出符合条件的 $P_j-P_i$ 的最大值。

样例

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

7