У Ashish есть бинарная строка $$$s$$$ длины $$$n$$$, которую он хочет отсортировать в неубывающем порядке.

Он может выполнять следующую операцию:

1. Выберите подпоследовательность любой длины, элементы которой идут в невозрастающем порядке. Формально, выберите любое $$$k$$$ такое, что $$$1 \leq k \leq n$$$ и любую последовательность $$$k$$$ индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$ такую, что $$$s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$$$.
2. Затем, «разверните» эту последовательность. Формально, поменяйте местами $$$s_{i_1}$$$ с $$$s_{i_k}$$$, $$$s_{i_2}$$$ с $$$s_{i_{k-1}}$$$, $$$\ldots$$$ и $$$s_{i_{\lfloor k/2 \rfloor}}$$$ с $$$s_{i_{\lceil k/2 \rceil + 1}}$$$ (Здесь $$$\lfloor x \rfloor$$$ обозначает наибольшее целое число, не превосходящее $$$x$$$, а $$$\lceil x \rceil$$$ обозначает наименьшее целое число, не меньшее $$$x$$$).

Найдите минимальное количество операций, необходимых для того, чтобы отсортировать строку в неубывающем порядке. Можно доказать, что всегда можно отсортировать заданную бинарную строку не более чем за $$$n$$$ операций.