{"extraResources":{"example.01.mu":"TVXzATUNCiFjMTs1DQpiZGNlZg0KIWMyOzMNCmhnZg0KIWMzOzcNCmRiYmRjYXoNCiFjNDs0DQpjYmFiDQohYzU7OA0KYWJlYmJjYWINCg=="},"scoring":null,"notes":"В первом наборе входных данных ряд меняется следующим образом : `bdcef' $\\rightarrow$ `bcef' $\\rightarrow$ `bef' $\\rightarrow$ `be'\r\n\r\nВ третьем наборе входных данных ряд меняется следующим образом : `dbbdcaz' $\\rightarrow$ `dbbcaz' $\\rightarrow$ `dbbaz' $\\rightarrow$ `dbaz' $\\rightarrow$ `daz'","legend":"Совет топ-менеджеров одной известной IT компании решил, что для повышения эффективности работы необходимо улучшить взаимодействие между командами. Для этого в пятницу было организовано мероприятие по сплочению сотрудников. На мероприятие собрали сотрудников из 26 команд, каждая из которых обозначалась уникальной латинской буквой от `a' до `z'. Затем всех сотрудников, пришедших на мероприятие, выстроили в ряд. Для каждого сотрудника записали букву, соответствующую его команде, в результате чего получилась строка длины $n$, состоящая из латинских строчных символов.\r\n\r\nСотрудники из одной команды уже знакомы друг с другом, поэтому целью мероприятия стало познакомить людей из разных команд. Поскольку сотрудников было слишком много, решено было знакомить только тех программистов, которые являются соседями в ряду и работают в соседних командах. Соседними командами являются те, чьи буквы расположены подряд в алфавите. Например, `a' и `b', `e' и `d' --- это пары соседних команд, а `z' и `a', `d' и `f', `t' и `t' соседними не считаются.\r\n\r\nДля того чтобы процесс знакомства был более организованным и последовательным, было решено следующее: среди всех соседей, которые соответствуют условию для знакомства, выбиралась первая подходящая пара. Затем один из сотрудников этой пары исключался из ряда, а остальные сдвигались, занимая его место. При этом исключался сотрудник с буквой, которая идет позже в алфавите --- то есть из пары удалялся сотрудник с максимальной буквой, а оставался тот, чья буква идет раньше в алфавите. Это правило позволяло сохранять упорядоченность строки и помогало равномерно знакомить сотрудников из разных команд.\r\n\r\nВсе детали были продуманы, теперь осталось понять, какая последовательность сотрудников останется в конце, для этого к вам обратились за помощью.","authorLogin":"robivirt","language":"russian","timeLimit":1000,"output":"Для каждого набора входных данных выведите команды оставшихся людей в ряду.","inputFile":"stdin","outputFile":"stdout","input":"В первой строке дано целое число $t$ ($1 \\le t \\le 10^4$)~--- количество наборов входных данных.\r\n\r\nДалее следуют описания наборов.\r\n\r\nВ первой строке дано целое число $n$ ($1 \\le n \\le 2 \\cdot 10^5$)~--- количество сотрудников на мероприятии.\r\n\r\nВо второй строке вводится строка из $n$ латинских строчных символов $s_1s_2\\ldots s_{n}$ ~--- последовательность команд сотрудников в ряду.\r\n\r\nГарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2\\cdot 10^5$.","authorName":"Viktor Krivoshchekov","sampleTests":[{"output":"be\r\nf\r\ndaz\r\na\r\naea\r\n","input":"5\r\n5\r\nbdcef\r\n3\r\nhgf\r\n7\r\ndbbdcaz\r\n4\r\ncbab\r\n8\r\nabebbcab\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Сплоченность в IT","interaction":null,"memoryLimit":268435456,"tutorial":"Мысленно запомним, какие пары индексы в течение работы алгоритма стали соседними командами. На пример, для строки `bdcef' такими парами были $(1, 2), (0, 2), (3, 4)$. Тогда можем заметить, что эти пары отсортированы по второму элементу в паре. Это верно, так как по условию всегда удаляется самая левая пара, и если после текущей пары существует пара с меньшим вторым индексом, то могли и до этого ее обработать. Поэтому получается следующая идея алгоритма.\r\n\r\nБудем перебирать второй индекс в паре от 0 до $n - 1$ и будем поддерживать текущий префикс строки после удалений. Тогда текущий индекс может быть в паре только с последним символом строки. Если они не образуют пару, то добавим текущий символ в конец строки и перейдем к следующему символу. Если текущий символ это меньший символ в паре, то должны его удалить, текущая строка не меняется, и переходим к следующему символу. Иначе удалим последний символ строки и снова рассмотрим случаи уже с новым последним символом. \r\n\r\nРеализовать данный алгоритм можем с помощью стека. Итоговая сложность будет $O(n)$, так как обрабатываем каждый символ не более одного раза и удаляем каждый символ тоже не более одного раза."}