Задана перестановка \(p\) длины \(n\).
Вы можете выполнять операции двух типов:
Ваша задача — для каждого целого числа от \(1\) до \((n-1)\) посчитать минимальное количество вышеописанных операций, чтобы удалить это число из перестановки.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число \(n\) (\(2 \le n \le 250\,000\)).
Вторая строка каждого набора содержит \(n\) целых чисел \(p_1, p_2, \dots, p_n\) (\(1 \le p_i \le n\)). Массив \(p\) является перестановкой.
Дополнительные ограничения на входные данные: сумма \(n\) по всем наборам входных данных не превосходит \(250\,000\).
Для каждого набора выведите \((n-1)\) целых чисел, \(i\)-е из которых — минимальное количество вышеописанных операций, чтобы удалить число \(i\) из перестановки.
5 4 4 2 1 3 2 1 2 6 5 4 1 3 2 6 7 5 6 1 3 7 2 4 5 3 1 2 5 4
1 1 2 1 1 1 2 1 3 1 1 1 2 1 2 1 1 2 1
5000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач