Задача №115178. Телефонный справочник
Саша недавно начала регистровать компанию по разработке чат-ботов и уже подала необходимые документы. Но добрые люди рассказали Саше, что в телефонном справочнике компании располагаются в лексикографически возрастающем порядке их названий. Что такое телефонный справочник, Саша не знает, но решила учесть рекомендации и поменять название своей компании, чтобы оно было как можно раньше в телефонном справочнике. Поскольку Саша уже подала документы, она не может полностью поменять название компании, но может сказать, что допустила опечатку, и поменять любые две буквы в названии местами. Помогите Саше выбрать новое название компании или оставить текущее.
В единственной строке содержится одно слово, состоящее из строчных латинских букв (от «a» до «z») длиной \(n\) (\(2 \leq n \leq 10^6\)).
Выведите одно слово — новое название компании. Если название не изменилось, выведите изначальное название.
Решения, верно работающие при \(n \leq 10\), будут оцениваться в \(20\) баллов.
Решения, верно работающие при \(n \leq 100\), будут оцениваться в \(40\) баллов.
Решения, верно работающие при \(n \leq 3\,000\), будут оцениваться в \(60\) баллов.
Решения, верно работающие при \(n \leq 50\,000\), будут оцениваться в \(80\) баллов.
aefbz
abfez
abc
abc