Постройка ворот
Фермер Джон строит изгородь.
ФД начинает в позиции (0, 0) и делает n шагов, двигаясь каждый раз на Единицу расстояния на север, юг, восток или запад. Каждый раз, когда он делает шаг, он строит изгородь за собой. Например, если первый его шаг будет на север, он добавит сегмент изгороди от (0, 0) до (0, 1). ФД может посещать точки повторно много раз и даже может строить одни и те же отрезки изгороди много раз. Его изгородь может даже пересекать себя много раз.
ФД в результате может разделить изгородями ферму на несколько независимых огороженных участков. Он хочет добавить двери для исправления такого положения. Дверь может быть установлена на любом отрезке единичной длины, так чтобы разрешить проход между двумя сторонами этого отрезка.
Определите минимальное количество дверей которые требуется построить, так чтобы каждый регион был доступен из каждого другого региона.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 1000). Следующая строка содержит строку длины n, описывающую путь ФД. Каждый символ один из N (север), E (восток), S (юг), W (запад).
Выходные данные
Выведите минимальное количество ворот, которое должен построить ФД, чтобы восстановить полную связность всех регионов своей фермы. Заметим, что ответ может быть 0, если ферма изначально связная.