Робин Гуд, как известно, крадет у богатых и раздает награбленное бедным. Правда в этот раз, к сожалению, ему придется обойтись только грабежом, потому что в городе, в который он прибыл, живут только богатые люди. Всего в городе живет $$$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$$$, которые минимизируют его несправедливость, выберите то, при котором размер награбленного максимален.