Fair Photography

Time limit1sMemory limit128 MB

Summary

Cows at distinct positions are white or spotted, and after repainting some white cows you need the widest interval with equal counts.

Level: Medium6 of 10
Topics: Prefix sum, Hash map, Sorting
Solved: No attempts yet

Problem

$N$ cows stand along a fence at distinct positions. Each is white (W) or spotted (S). You may paint some white cows spotted so an interval photo can have equal counts.

Photo size is max position minus min position among included cows. Find the maximum fair photo size.

Input

Line 1: $N$ .

Next $N$ lines: position $x_i$ and W or S.

Output

Maximum photo size.

Examples1

Example 1
Input
```
5
8 W
11 S
3 W
10 W
5 S
```
Expected output
```
7
```