Вам дана строка $$$s$$$, состоящая из $$$n$$$ строчных букв латинского алфавита.
Подстрока строки — это некоторый ее непрерывный подотрезок. Например, «acab» — подстрока строки «abacaba» (она начинается в позиции $$$3$$$ и заканчивается в позиции $$$6$$$), но «aa» и «d» не являются подстроками этой строки. То есть подстрока строки $$$s$$$ с позиции $$$l$$$ по позицию $$$r$$$ — это строка $$$s[l; r] = s_l s_{l + 1} \dots s_r$$$.
Вам нужно выбрать ровно одну подстроку данной строки и развернуть ее (то есть сделать $$$s[l; r] = s_r s_{r - 1} \dots s_l$$$), чтобы полученная строка оказалась лексикографически меньше исходной. Обратите внимание, что не обязательно минимизировать полученную строку.
Если невозможно таким образом развернуть подстроку, выведите «NO». Иначе выведите «YES» и любую подходящую подстроку.
Строка $$$x$$$ лексикографически меньше строки $$$y$$$, если либо $$$x$$$ является префиксом $$$y$$$ (и при этом $$$x \ne y$$$), либо существует такое $$$i$$$ ($$$1 \le i \le min(|x|, |y|)$$$), что $$$x_i < y_i$$$, и для любого $$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$. Здесь $$$|a|$$$ обозначает длину строки $$$a$$$. Лексикографическое сравнение строк реализует оператор < в современных языках программирования.
В первой строке входных данных задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — длина строки $$$s$$$.
Во второй строке записана $$$s$$$ — строка из $$$n$$$ строчных букв латинского алфавита.
Если невозможно развернуть подстроку так, чтобы в итоге получилась строка лексикографически меньше исходной, выведите «NO». Иначе выведите «YES» и два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$), обозначающие начало и конец подстроки, которую вы хотите перевернуть. Если ответов несколько, выведите любой из них.
7 abacaba
YES 2 5
6 aabcfg
NO
В первом тесте после разворота подстроки получается строка «aacabba».
Название |
---|