Задано два целочисленных массива: массив \(a\) размера \(n\) и массив \(b\) размера \(n+1\).
Вы можете выполнять следующие операции любое количество раз в любом порядке:
Ваша задача — посчитать минимальное количество вышеописанных операций (возможно, нулевое), необходимых для преобразования массива \(a\) в массив \(b\). Можно показать, что при ограничениях задачи это всегда возможно.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из трех строк:
Дополнительное ограничение на входные данные: сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных, выведите одно целое число — минимальное количество вышеописанных операций (возможно, нулевое), необходимых для преобразования массива \(a\) в массив \(b\).
В первом примере вы можете преобразовать \(a\) в \(b\) следующим образом: \([2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]\).
3 1 2 1 3 2 3 3 3 3 3 4 4 2 1 2 2 1 5 2 3
3 1 8
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач