N (2 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и является либо чисто белой коровой, либо коровой с пятном. Никакие две коровы не занимают одну и ту же позицию и имеется хотя бы одна белая корова.
ФД хочет сделать фото непрерывного интервала коров, так чтобы на фото было одинаковое количество белых и пятнистых коров. ФД хочет определить максимальный размер такого фото, где размер равен разности между максимальной и минимальной позициями коров на фото.
Чтобы дать себе шанс увеличить размер фото, ФД может пририсовать пятно произвольному подмножеству белах коров, тем самым превращая их в пятнистых.
Пожалуйста, определите наибольший размер фото, которое ФД может сделать, с учётом возможности перекрашивания коров из белых в пятнистые. (Конечно, ФД может и не красить коров, если ему так выгоднее)
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и либо W (для белой коровы) либо S (для пятнистой коровы).
Примечание
Всего есть 5 коров. Одна из них белая на позиции 8 и т.д. Формат вывода:
* Строка 1: Максимальный размер фото, которое может сделать ФД с учётом возможности перекрашивания белых коров в пятнистых.
Примечание
ФД фотографирует коров с позиции 3 по позицию 10. В этом интервале имеется 4 коровы 3 белых и 1 пятнистая, поэтому он перекрасит одну корову из белых в пятнистую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8 W
11 S
3 W
10 W
5 S
|
7
|