30752번 - Трудовые будни 스페셜 저지다국어

Бригадир Павел руководит командой рабочих, занимающихся возведением концертного зала по новейшему проекту иностранных архитекторов. Главной особенностью здания должна стать колоннада у главного входа, состоящая из $n$ колонн. При этом, каждая из колонн, вопреки классическим архитектурным представлениям, будет иметь свою высоту, не совпадающую с высотой крыши над входом. По текущему плану высоты колонн составляют $a_1, a_2, \ldots, a_n$ метров относительно уровня крыши в порядке следования слева направо (например, высота в $10$ метров означает, что колонна выдаётся на десять метров над крышей, а высота в $-5$ метров означает, что между верхом колонны и крышей остаётся зазор в пять метров).

За три дня до сдачи объекта и торжественного открытия зала архитекторы прибыли на место строительства и изменили проект, выдвинув новое требование: в соответствии с последними веяниями европейской моды разность высот любых двух соседних колонн должна быть одной и той же, то есть, для любых двух целых $i$ и $j$ от $1$ до $n - 1$ должно выполняться условие: $a_{i+1} - a_i = a_{j+1} - a_j$. Точное значение высоты каждой колонны при этом не имеет значения. По техническим причинам колонны могут только иметь высоту, выражающуюся целым числом метров относительно уровня крыши.

Изменение высоты колонны на $x$ метров как в сторону увеличения, так и в сторону уменьшения, будет стоить $x$ бурлей. Павел просит вас помочь ему выбрать новую высоту для каждой колонны так, чтобы выполнить поставленное требование и затратить при этом суммарно как можно меньше денег на изменение высот колонн. Помогите ему, или его больше никогда не будут приглашать возводить здания по иностранным проектам.

В первой строке входных даных находится целое число $n$ ($2 \leq n \leq 3\,000\,000$) --- количество колонн перед входом в здание.

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

Выведите два целых числа: высоту первой колонны и разность высот между двумя соседними колоннами в оптимальном плане.

Абсолютная величина обоих выведенных чисел не должна превышать $10^{16}$. Гарантируется, что существует оптимальный ответ, удовлетворяющий этому условию.

В первом тесте из условия менять высоту колонн не требуется, так как их всего две, и они автоматически удовлетворяют поставленному требованию.

Во втором тесте из условия оптимальным набором высот колонн будет $3, 7, 11, 15, 19$, а суммарная стоимость изменений есть $|3 - 3| + |7 - 8| + |11 - 10| + |15 - 13| + |19 - 20| = 5$.