Нарек должен провести 2 часа с детьми в детском саду. Он хочет научить их спортивному программированию, и их первый урок посвящен палиндромам.
Нарек выяснил, что дети знают только гласные буквы английского алфавита (буквы \(\mathtt{a}\), \(\mathtt{e}\), \(\mathtt{i}\), \(\mathtt{o}\) и \(\mathtt{u}\)), поэтому Нареку нужно составить строку, состоящую только из гласных. После составления строки он попросит детей посчитать количество подпоследовательностей, которые являются палиндромами. Нарек хочет, чтобы это было просто, поэтому он ищет строку, для которой количество палиндромных подпоследовательностей минимально.
Помогите Нареку найти строку длины \(n\), состоящую из строчных гласных латинских букв (буквы \(\mathtt{a}\), \(\mathtt{e}\), \(\mathtt{i}\), \(\mathtt{o}\) и \(\mathtt{u}\)), которая минимизирует количество палиндромных\(^{\dagger}\) подпоследовательностей\(^{\ddagger}\) в ней.
\(^{\dagger}\) Строка называется палиндромом, если она читается одинаково слева направо и справа налево.
\(^{\ddagger}\) Строка \(t\) является подпоследовательностью строки \(s\), если \(t\) можно получить из \(s\) путем удаления нескольких (возможно, ни одного или всех) символов из \(s\) и конкатенации оставшихся, не меняя их порядок. Например, \(\mathtt{odocs}\) является подпоследовательностью \(\texttt{c}{\color{red}{\texttt{od}}}\texttt{ef}{\color{red}{\texttt{o}}}\texttt{r}{\color{red}{\texttt{c}}}\texttt{e}{\color{red}{\texttt{s}}}\).
Примечание
В первом примере \(\texttt{uo}\) имеет только три палиндромные подпоследовательности: \(\texttt{u}\), \(\texttt{o}\) и пустую строку. Можно показать, что нет ответа лучше.
В третьем примере \(\texttt{oeiiua}\) имеет только восемь палиндромных подпоследовательностей: \(\texttt{o}\), \(\texttt{e}\), \(\texttt{i}\), \(\texttt{i}\), \(\texttt{u}\), \(\texttt{a}\), \(\texttt{ii}\) и пустую строку. Можно показать, что нет ответа лучше.