У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Каждое число в этом массиве Вася считает по-своему необычным. Чтобы вычислить необычность числа на позиции \(i\), Вася делает следующее:
Он выбирает подотрезок \(a_l, a_{l+1}, \ldots, a_r\) такой, что \(1 \le l \le i \le r \le n\) и мысленно сортирует его по возрастанию (равные элементы он может переставлять так, как ему хочется). Далее на этом подотрезке он находит центр. Центром подотрезка называется элемент на позиции \((l + r) / 2\), если длина отрезка нечётна, или элемент на позиции \((l + r + 1) / 2\), если длина отрезка чётна. Теперь Вася находит на этом подотрезеке элемент, который до сортировки стоял на позиции \(i\), и смотрит на расстояние от этого элемента до центра подотрезка (расстояние между элементами с индексами \(j\) и \(k\) равняется \(|j - k|\)).
Необычностью числа на позиции \(i\) называется максимальное такое расстояние среди всех подходящих выборов \(l\) и \(r\).
Вася хочет посчитать необычность каждого числа в своём массиве. Помогите ему это сделать.