Задана перестановка \(p\) длины \(n\).
Вы можете выполнять операции двух типов:
- отметить все такие позиции \(i\), что \(1 \le i < n\) и \(p_i < p_{i + 1}\), и одновременно удалить элементы на этих позициях;
- отметить все такие позиции \(i\), что \(2 \le i \le n\) и \(p_{i - 1} > p_i\), и одновременно удалить элементы на этих позициях.
Ваша задача — для каждого целого числа от \(1\) до \((n-1)\) посчитать минимальное количество вышеописанных операций, чтобы удалить это число из перестановки.
Выходные данные
Для каждого набора выведите \((n-1)\) целых чисел, \(i\)-е из которых — минимальное количество вышеописанных операций, чтобы удалить число \(i\) из перестановки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|