Робин Гуд, как известно, крадет у богатых и раздает награбленное бедным. Правда в этот раз, к сожалению, ему придется обойтись только грабежом, потому что в городе, в который он прибыл, живут только богатые люди. Всего в городе живет \(n\) богатых людей, их дома расположены вдоль главной улицы города, в \(i\)-м доме живет человек с состоянием \(a_i\).

Поскольку Робин Гуд работает вместе с сообщниками, он собирается заранее составить план действий. План состоит из целого числа \(k\) и вещественного числа \(t\), которые означают, что будут ограблены дома с номерами \(k, k + 1, \ldots, n\), и из каждого из них будет украдена доля состояния \(t\). Иными словами, после исполнения такого плана состояния жителей будут равны \(\)a^\mathrm{new} = [a_1, a_2, \ldots, a_{k-1}, (1-t)a_k, (1-t)a_{k+1}, \ldots, (1-t)a_n],\(\) а размер награбленного будет равен \(\)b = t\cdot(a_k+a_{k+1}+\ldots+a_{n}).\(\)

Назовем несправедливостью после ограбления величину \(\max(a^\mathrm{new}) - \min(a^\mathrm{new})\) — разность между максимальным и минимальным состояниями жителей города после ограбления.

Поскольку банда Робина Гуда еще не прибыла целиком в город, он не знает, как много домов они успеют ограбить. Помогите ему для каждого \(k\) от \(1\) до \(n\) включительно определить, при каком \(t\) от \(0\) до \(1\) включительно несправедливость после ограбления по плану \((k, t)\) будет минимальна. Если для заданного \(k\) есть несколько значений \(t\), которые минимизируют его несправедливость, выберите то, при котором размер награбленного максимален.