Перед домом Элис есть песчаная дорожка.

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

Например, предположим, что один человек пошел по тропинке и оставил какие-то следы. Пусть следы имеют вид RRLRL в порядке следования по дорожке ('R' обозначает правую ногу, а 'L' обозначает левую ногу). Можно подумать, что это какая-то странная последовательность следов. Но на самом деле, некоторые следы остаются от ходьбы задом наперед!

Есть несколько возможных последовательностей шагов, после которых могли остаться такие следы, например 1 → 3 → 2 → 5 → 4 или 2 → 3 → 4 → 5 → 1 (мы считаем, что расстояние между двумя последовательными шагами может быть произвольным). В двух примерах, приведенных выше, было сделано 2 шага назад и 1 шаг назад соответственно.

Элис заинтересовали эти следы. Каждый раз, когда по дорожке проходит человека, она делает фотографию всех его следов, а затем стирает их все, таким образом, каждый следующий человек оставляет новый набор следов. Мы знаем, что люди ходят, наступая попеременно то правой, то левой ногой, но мы не знаем, с какой ноги делается первый шаг.

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