Назовем строку S правильной скобочной последовательностью, если она состоит только из символов '{', '}', '[', ']', '(', ')' и выполнено хотя бы одно из следующих трех условий:

1) S — пустая строка;

2) S можно представить в виде S=S₁+S₂+S₃+...+S_N (N>1), где S_i — непустые правильные скобочные последовательности, а знак "+" обозначает конкатенацию (приписывание) строк;

3) S можно представить в виде S='{'+C+'}' или S='['+C+']' или S='('+C+')', где C является правильной скобочной последовательностью.

Дана строка, состоящая только из символов '{', '}', '[', ']', '(', ')'. Требуется определить, какое минимальное количество символов надо вставить в эту строку для того, чтобы она стала правильной скобочной последовательностью.

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте h_i. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x₁-ом, x₂-ом, …, x_2k+1-ом (x₁ < x₂ < … < x_2k+1)) дне, то должно выполняться условие h_x1 < h_x2 < … < h_xk < h_xk+1 > h_xk+2 > … > h_x2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.