E. Макс и выдача багажа

Финальный турнир сезона «Зима — 2022»

Старт: 05.мар.2022 в 10:15:00
Финиш: 05.мар.2022 в 13:15:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и розыгрыш приза
• B. Макс и перемешанные фотографии
• C. Макс и офисная улица
• D. Макс и дуэль танков
• E. Макс и выдача багажа
• F. Макс и A0
• G. Макс и шкафчик
• H. Макс и тройные подарки

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/3000/3000/3000 мс. Лимит памяти 132000/132000/132000/132000 Кб.

Макс и выдача багажа

Макс устроился на работу в аэропорт, и ему сразу поручили ответственное дело — выдачу багажа.

Всего Максу нужно выдать $$$N$$$ чемоданов $$$M$$$ пассажирам. После посадки самолёта Макс укладывает чемоданы в стопки, следуя двум правилам:

Макс может брать чемоданы только в том порядке, в котором они расположены в багажном отделе самолёта;
Макс может положить чемодан только на вершину одной из стопок.

После того, как Макс разложит все чемоданы по стопкам, из самолёта начинают выходить пассажиры, причём выходят они строго по порядку — сначала пассажир с номером $$$1$$$, потом с номером $$$2$$$ и так далее.

Каждый пассажир, подходя к стопкам, забирает все свои чемоданы, однако брать чемоданы он может только с вершин стопок (если несколько его чемоданов находятся в одной стопке, они все должны быть на самом верху). Если же его чемоданы не находятся на вершинах стопок, то он будет просить Макса о помощи.

Перед прилётом очередного самолёта Макс задумался, на какое минимальное количество стопок можно разложить чемоданы, чтобы все пассажиры смогли забрать свой багаж, не прося о помощи Макса. Помогите ему найти ответ на этот вопрос.

Входные данные

Первая строка содержит целое число $$$T$$$ ($$$1 \le T \le 10^5$$$) — количество самолётов.

Следующие $$$(2 \cdot T)$$$ строк описывают самолёты.

Первая строка каждой пары содержит целые числа $$$N$$$ и $$$M$$$ ($$$1 \le M \le N \le 3 \cdot 10^5$$$) — соответственно количество чемоданов и количество пассажиров.

Вторая строка каждой пары содержит $$$N$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le M$$$) — номера пассажиров, которым принадлежат чемоданы.

Гарантируется, что сумма $$$N$$$ по всем тестам не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого самолёта выведите одно целое число — минимальное количество стопок, по которым можно разложить чемоданы так, чтобы все пассажиры смогли их забрать.

Пример