Прогулка

Юный Скебоп любит гулять после школы. А ещё он просто помешан на эффективности! Именно поэтому на сегодняшней прогулке он записывал направление каждого своего шага. Шагал он только налево, направо, вверх и вниз, никогда не поворачиваясь. После своей прогулки Скебоп принес вам записи своих шагов и попросил помочь ему: он хотел бы оптимизировать этот план прогулки так, чтобы этот маршрут был кратчайшим от стартовой точки до какой-то другой, и при всём при этом удалить наименьшее количество шагов из маршрута. Помогите ему и ответьте, какое минимальное количество шагов нужно удалить, чтобы удовлетворить требованиям Скебона?

Более формально, на вход подается строка, состоящая из символов U, D, R, L — направления шагов (вверх, вниз, вправо и влево соответственно). Выведите минимальное количество символов, которое нужно удалить из этой строки, чтобы она стала кратчайшим путем между стартовой и конечной точкой.

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

В первой строке входного файла INPUT.TXT содержится целое число N — количество шагов.

Во второй строке содержится строка S длины N, состоящая из символов U, D, R, L.

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

В выходной файл OUTPUT.TXT выведите минимальное количество символов, удалив которые строка будет кратчайшим путём.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!