B. Просто сидим на стульях
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд стоит $$$n$$$ стульев, изначально все они не помечены.

Вам дана перестановка $$$p$$$$$$^{\text{∗}}$$$ длины $$$n$$$.

Вы играете в игру. Вы последовательно посещаете каждый стул, начиная с $$$1$$$-го. На $$$i$$$-м стуле вы можете сделать следующее:

  • Если $$$i$$$-й стул уже помечен, то вы немедленно заканчиваете игру, не садясь на него.
  • Иначе вы можете либо сесть на этот стул, либо пропустить его и перейти к следующему.
  • Если вы решаете сесть на стул, то после того, как встанете, вы помечаете $$$p_i$$$-й стул и переходите к следующему.

Игра также заканчивается, если вы посетите все $$$n$$$ стульев.

Ваша задача — определить максимальное количество стульев, на которые вы можете сесть.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество стульев.

Вторая строка каждого набора входных данных содержит $$$n$$$ попарно различных целых чисел $$$p_1, p_2,\ldots,p_{n}$$$ — перестановку $$$p$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Выведите одно целое число — максимальное количество стульев, на которые вы можете сесть.

Пример
Входные данные
4
3
3 2 1
5
4 3 2 5 1
4
4 2 1 3
4
2 3 4 1
Выходные данные
2
2
3
1
Примечание

В первом наборе входных данных можно действовать следующим образом:

  1. Вы посещаете $$$1$$$-й стул, садитесь на него и помечаете $$$3$$$-й стул.
  2. Вы посещаете $$$2$$$-й стул, садитесь на него и помечаете $$$2$$$-й стул.
  3. Вы посещаете $$$3$$$-й стул. Поскольку он помечен, вы заканчиваете игру.
Следовательно, при такой последовательности действий вы можете сесть в сумме на $$$2$$$ стула. Можно показать, что максимальное количество стульев, на которые можно сесть при любой последовательности действий, равно $$$2$$$.

Во втором наборе входных данных можно действовать следующим образом:

  1. Вы посещаете $$$1$$$-й стул, садитесь на него и помечаете $$$4$$$-й стул.
  2. Вы посещаете $$$2$$$-й стул и пропускаете его.
  3. Вы посещаете $$$3$$$-й стул, садитесь на него и помечаете $$$2$$$-й стул.
  4. Вы посещаете $$$4$$$-й стул. Поскольку он помечен, вы заканчиваете игру.
Следовательно, при такой последовательности действий вы можете сесть в сумме на $$$2$$$ стула. Можно показать, что максимальное количество стульев, на которые можно сесть при любой последовательности действий, равно $$$2$$$.