Республиканская олимпиада по информатике 2020 года за 11 класс | Казахстанские олимпиады

Сбалансированные подпоследовательности

У Есмахана есть массив $a$ размера $n$.

Сбалансированность массива определяется как абсолютная разность между:

• максимумом по всем числам, стоящим на нечетных позициях.

• максимумом по всем числам, стоящим на четных позициях.

Например, сбалансированность масиива $b =[2, 5, 3, 4, 2]$ равно $|max(2, 3, 2) − max(5, 4)| = 2$.

Для каждого $k$ от $2$ до $n$, найдите минимальную сбалансированность среди всех подпоследовательностей массива $a$ размера $k$.

Подпоследовательностью массива $a$ называется массив, который получается из $a$ удалением некоторых элементов.

Формат входного файла

В первой строке находится одно целое число $n(2 \leq n \leq 3 * 10^5)$.

Во второй строке находятся $n$ целых числа $a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)$.

Формат выходного файла

Выведите $n − 1$ чисел : ответ для каждого $k$ от $2$ до $n$.

Примеры

Ввод

5
5 1 7 1 5

Вывод

0 2 0 6

Ввод

10
69 78 22 33 24 7 41 36 50 67

Вывод

2 2 2 3 2 9 2 9 9