1 группа
Для каждого запроса промоделируем процесс удаления. На каждом этапе будем искать последовательность рекордов и запоминать элементы, которые мы уже удалили. Получаем асимптотику $$$O(nk)$$$ на один запрос и $$$O(qnk)$$$ итоговую.
2 группа
В данной группе перестановка отсортирована по убыванию. Рассмотрим произвольный запрос. Заметим, что на каждом этапе удаления длина последовательности рекордов не превосходит $$$1$$$. Если мы совершаем $$$k$$$ этапов удаления, то ответ это минимум из $$$k$$$ и количества чисел на суффиксе.
3 группа
Сохраним для каждой позиции перестановки все запросы, суффиксы которых начинаются в этой позиции. Будем перебирать индекс перестановки от конца к началу и отвечать сразу на все запросы для одной позиции. Для решения этой группы заведем стек рекордов. При переходе от позиции $$$i$$$ к позиции $$$i - 1$$$ удалим с верхушки стека все элементы, меньшие $$$a_{i - 1}$$$ и положим $$$a_{i - 1}$$$ в стек (т.к. $$$a_{i - 1}$$$ точно окажется в последовательности рекордов на первом этапе удаления). Чтобы узнать длину последовательности рекордов, посмотрим на размер стека. Каждый элемент попадает в стек ровно один раз и будет удален из стека не более одного раза, поэтому итоговая асимптотика $$$O(n + q)$$$.
4 группа
Улучшим решение для предыдущей группы. Вместо одного стека будем поддерживать два — в первом будет храниться последовательность рекордов для текущего суффикса, а во втором последовательность рекордов, если совершить $$$1$$$ этап удаления. Посмотрим на те элементы, которые были удалены из первого стека при переходе от $$$i$$$ к $$$i - 1$$$. Заметим, что эти элементы неизбежно окажутся в последовательности рекордов после первого этапа удаления. Мы добавим их во второй стек, но перед этим нужно понять, какие элементы могут перестать входить в последовательность рекордов после первого этапа удаления. На самом деле, это все те элементы, что не превосходят максимум среди добавляемых элементов. Удалим все эти значения из второго стека и положим новые. Это легко сделать, так как значения в стеках идут в возрастающем порядке. Можно заметить, что после такой процедуры значения в стеках по-прежнему будут идти в возрастающем порядке.
5 группа
Воспользуемся тем, что $$$k$$$ в любом запросе не превосходит $$$20$$$. Обобщим идеи для прошлых групп и заведем сразу $$$20$$$ стеков. В $$$i$$$-м стеке будет лежать последовательность рекордов после $$$i - 1$$$ этапа удалений. При добавлении нового элемента обновим первый стек, а дальше будем идти стекам, начиная со второго, и обновлять их через те элементы, которые были выброшены из предыдущего стека. Если на каком-то шаге мы не выбросили ни одного элемента, прекратим этот процесс. Для ответа на запрос посчитаем сумму размеров первых $$$k$$$ стеков. Каждый элемент добавится в каждый стек и удалится из каждого стека не более одного раза, поэтому итоговая асимптотика $$$O(nk + qk)$$$.