Миим и Шааш как обычно после уроков решили во что-нибудь поиграть. Идя после школы, они увидели игру Классики, в которую они часто играли в детстве. Но они уже взрослые, поэтому нужна новая игра, и в эту игру должно быть интересно играть вдвоем. Также им очень нравятся палиндромы, поэтому в игре они должны быть обязательно. Миим предложил сделать игру со строкой. Шааш захотел, чтобы игра была активной. В результате они получили шедевр, который назвали Игра 2.
Вначале игры они выкладывают бинарную строку длины $$$n$$$. Затем Миим начинает идти от начала до конца строки, посетив каждый символ один раз. У него есть два варианта действий : либо перейти к следующему символу, либо сказать Шаашу, что он должен стать на произвольном символе строки перед Миимом, после этого они меняются символами. Их цель в конце сделать строку палиндромом.
После нескольких игр они устали и захотели показать в школе, что они придумали. К сожалению, они не записали свои ходы, а без них будет менее интересно. Помогите им понять, как могла проходить игра.
В первой строке входных данных дано целое число $$$n$$$ — длина строки $$$(1 \le n \le 2 \cdot 10^5)$$$.
Во второй строке дана строка длины $$$n$$$ из 0 и 1.
Если способа победить не было, то выведите «NO». В ином случае выведите «YES», если друзья могли выиграть. В следующей строке выведите число $$$m$$$ — количество обменов символов. В следующих $$$m$$$ строках пары чисел $$$l_i \lt r_i$$$ — их позиции на строке во время обмена.
Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 10 | $$$n \le 7$$$ | |
| 2 | 12 | $$$n \le 2\cdot 10^5$$$, размер ответа не более двух | |
| 3 | 29 | $$$n \le 1000$$$ | 1 |
| 4 | 15 | символы строки расположены в порядке неубывания | |
| 5 | 34 | $$$n \le 2 \cdot 10^5$$$ | 1–4 |
3001
YES 1 2 3
801010101
YES 2 1 2 3 4
