Las ~N~ vacas del Granjero Juan ~(1 \leq N \leq 100,000)~ están paradas en varias posiciones a lo largo de una cerca unidimensional. La iésima vaca está parada en la posición ~x_i~ (un entero en el rango ~0..1,000,000,000~) y tiene raza ~b_i~ (o ~G~ para Guernsey o ~H~ para Holstein). No hay dos vacas que ocupen la misma posición.

GJ quiere tomar una foto de un intervalo contiguo de vacas para la feria del condado, pero él quiere que sus razas estén representadas balanceadamente en la foto. Por lo tanto, él quiere asegurarse que, para cualquier raza que esté presente en la foto, hay un número igual de cada raza (por ejemplo, una foto con todas Holsteins está bien, una foto con 27 Holsteins y 27 Guernseys está bien, pero una foto con 10 Holsteins y 9 Guernseys no está bien). Ayude a GJ a tomar su foto de feria encontrando el tamaño máximo que satisfaga las restricciones de GJ. El tamaño de una foto es la diferencia entre las posiciones máxima y mínima en la foto. Es posible que GJ podría terminar tomando una foto con una sola vaca, en cuyo caso la foto tendría tamaño cero.

Entrada

• Línea 1: El entero ~N~.

• Líneas 2..1+N: La línea i+1 contiene ~x_i~ y ~b_i~.

Ejemplo de Entrada

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

Detalles de la Entrada: Hay seis vacas con razas (de izquierda a derecha) ~G, H, G, G, H, G~.

Salida

• Línea 1: Un solo entero indicando el tamaño máximo de la foto de feria.

Ejemplo de Salida

7

Detalles de la Salida: La foto más grande que el Granjero Juan puede tomar es de las 4 vacas del medio, conteniendo 2 Holsteins y 2 Guernseys.