J. Международный день скептиков
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ежегодно 14 ноября отмечается Международный день скептиков — праздник критического мышления, сомнений в очевидном и научной проверки любых утверждений.

К этому дню в музее занимательной науки иллюзионист подготовил оптический аттракцион, утверждая, что сложная система зеркал способна создавать принципиально новые и непостижимые иллюзии. В лабиринте аттракциона на плоскости установлена последовательность из $$$n$$$ оптических зеркал, которые луч лазера проходит строго по порядку:

  • операция V $$$a$$$ — вертикальное двустороннее зеркало, отражающее луч относительно прямой $$$x = a$$$: $$$(x, y) \to (2a - x, y)$$$;
  • операция H $$$a$$$ — горизонтальное двустороннее зеркало, отражающее луч относительно прямой $$$y = a$$$: $$$(x, y) \to (x, 2a - y)$$$;
  • операция D — диагональное полупрозрачное зеркало, отражающее луч относительно прямой $$$y = x$$$ (меняющее координаты местами): $$$(x, y) \to (y, x)$$$.

Учёный-скептик, пришедший на выставку, сразу заподозрил фокусника в избыточном усложнении конструкции. Скептик утверждает, что многие зеркала установлены лишь для создания ложной видимости сложности. Чтобы доказать это на практике, он хочет убрать ровно один непустой непрерывный фрагмент подряд идущих зеркал с номерами от $$$l$$$ до $$$r$$$ ($$$1 \le l \le r \le n$$$) так, чтобы для любой начальной точки лазерного луча $$$(x, y)$$$ его итоговое положение после прохождения оставшихся зеркал (в прежнем порядке) осталось в точности таким же, как и при прохождении всех $$$n$$$ зеркал.

Помогите скептику разоблачить иллюзиониста: посчитайте количество таких непустых непрерывных фрагментов $$$[l, r]$$$, удаление которых никак не влияет на итоговое оптическое преобразование плоскости.

Входные данные

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество зеркальных преобразований.

В следующих $$$n$$$ строках описаны операции в порядке их выполнения. Каждая строка имеет один из трёх видов:

  • «V $$$a$$$» ($$$-10^9 \le a \le 10^9$$$) — отражение относительно прямой $$$x = a$$$;
  • «H $$$a$$$» ($$$-10^9 \le a \le 10^9$$$) — отражение относительно прямой $$$y = a$$$;
  • «D» — отражение относительно прямой $$$y = x$$$.
Все числа $$$a$$$ — целые.
Выходные данные

Выведите одно целое число — количество непустых непрерывных фрагментов операций, удаление которых сохраняет итоговое преобразование для любой начальной точки.

Примеры
Входные данные
4
V 2
H -1
V 2
H -1
Выходные данные
1
Входные данные
4
D
V 5
D
H 5
Выходные данные
1
Входные данные
5
V 3
V 3
V 3
D
D
Выходные данные
4
Примечание

В первом примере вертикальное отражение относительно $$$x = 2$$$ и горизонтальное отражение относительно $$$y = -1$$$ независимы по координатам и коммутируют, поэтому применение всех четырёх операций возвращает любую точку $$$(x, y)$$$ на исходное место: $$$(T_4 = T_0)$$$. Скептик может убрать весь фрагмент $$$[1, 4]$$$ целиком — удаление любого другого подотрезка изменит итоговое положение луча.

Во втором примере иллюзионист попытался замаскировать горизонтальное отражение H 5 с помощью диагональных зеркал: $$$$$$(x, y) \xrightarrow{\t{D}} (y, x) \xrightarrow{\t{V 5}} (10 - y, x) \xrightarrow{\t{D}} (x, 10 - y).$$$$$$ Композиция первых трёх зеркал в точности эквивалентна H 5. Вместе с четвёртым зеркалом H 5 они взаимно уничтожаются, поэтому удаление всего фрагмента $$$[1, 4]$$$ сохраняет итоговое преобразование.

В третьем примере подходящими являются $$$4$$$ фрагмента: $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[4, 5]$$$ и $$$[2, 5]$$$. Например, удаление фрагмента $$$[1, 2]$$$ оставляет зеркала $$$3, 4, 5$$$ (V 3, D, D), что даёт то же итоговое отображение V 3, что и исходная последовательность из пяти зеркал.