Фермер Джон недавно закупил n коров, каждая из которых имеет породу Guernsey или Holstein.

Эти коровы сейчас стоят в ряд и ФД хочет сделать фото каждой последовательности из трёх или более последовательных коров. Однако он не хочет делать фото, в котором ровно одна корова породы Guernsey или ровно одна корова породы Holstein - он считает, что эта одна корова будет чувствовать себя изолированной. После взятия фото каждой последовательности из трёх или более коров, он выбрасывает так называемые "одинокие" фото, на которых ровно одна корова породы Guernsey или ровно одна корова породы Holstein.

По заданному порядку коров, помогите ФД определить, сколько "одиноких" фото он выбросит. Два фото считаются различными, если они начинаются или заканчиваются на различных коровах в ряду.

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

Строка содержит одно число n (3 ≤ n ≤ 5 * 105).

Вторая строка содержит строку из n символов. i-ый символ есть G если соответствующая корова имеет породу Guernsey, и H, если соответствующая корова имеет породу Holstein.

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

Выведите количество фотографий, которые ФД выбросит.

Пример

Каждая подстрока длины 3 в этом примере содержит ровно одну корову породы Guernsey или ровно одну корову породы Holstein - поэтому эти подстроки представляют "одинокие" фотографии, которые должны быть выброшены. Все более длинные строки (GHGH, HGHG, GHGHG) приемлемы для ФД.