hello
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
template <class F>
struct ycr {
F f;
template <class T>
explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F>
decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
template <class T> void setmax(T& a, const T& b) {
if (a < b) a = b;
}
template <class T> void setmin(T& a, const T& b) {
if (a > b) a = b;
}
template <class T> ostream& operator << (ostream& os, const vector<T>& A) {
assert(!A.empty());
int N = int(A.size());
for (int i = 0; i < N; i++) {
os << A[i];
if (i+1 < N) {
os << ' ';
}
}
return os;
}
const ll INF = 1.01e18;
template <class T>
vector<T> convolution(const vector<T>& A, const vector<T>& B) {
const int N = int(A.size());
const int M = int(B.size());
const int L = N+M-1;
vector<T> C(L, +INF);
{
int cur = 0;
int j = -1;
for (int i = 0; i < N; i++) {
if (A[i] == +INF) break;
while (j+1 < M && B[j+1] <= A[i]) {
j++;
}
if (j >= 0) {
while (cur <= i+j) {
setmin(C[cur++], A[i]);
}
}
}
}
{
int cur = 0;
int j = -1;
for (int i = 0; i < M; i++) {
if (B[i] == +INF) break;
while (j+1 < N && A[j+1] <= B[i]) {
j++;
}
if (j >= 0) {
while (cur <= i+j) {
setmin(C[cur++], B[i]);
}
}
}
}
cerr << "A = " << A << endl;
cerr << "B = " << B << endl;
cerr << "C = " << C << endl;
return C;
}
struct dp_t : array<array<vector<ll>, 2>, 2> {
dp_t() {}
dp_t(ll x) {
(*this)[0][0] = {0, +INF};
(*this)[0][1] = {+INF, +INF};
(*this)[1][0] = {+INF, +INF};
(*this)[1][1] = {+INF, x};
}
friend dp_t merge(const dp_t& l, const dp_t& r) {
dp_t res;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
auto f00 = convolution(l[a][0], r[0][b]);
auto f01 = convolution(l[a][0], r[1][b]);
auto f10 = convolution(l[a][1], r[0][b]);
const int L = int(f00.size());
res[a][b].resize(L);
for (int i = 0; i < L; i++) {
res[a][b][i] = min({f00[i], f01[i], f10[i]});
}
}
}
while (true) {
ll v = min({res[0][0].back(), res[0][1].back(),
res[1][0].back(), res[1][1].back()});
if (v == +INF) {
res[0][0].pop_back();
res[0][1].pop_back();
res[1][0].pop_back();
res[1][1].pop_back();
} else {
break;
}
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N; cin >> N;
vector<ll> A(N);
for (ll& a : A) cin >> a;
sort(A.begin(), A.end());
N--;
vector<dp_t> stuff(N);
for (int i = 0; i < N; i++) {
stuff[i] = dp_t(A[i+1] - A[i]);
cerr << A[i+1] - A[i] << " \n"[i+1==N];
}
auto res = yc([&](auto self, int l, int r) -> dp_t {
if (l+1 == r) {
return stuff[l];
} else {
int m = (l+r)/2;
return merge(self(l, m), self(m, r));
}
})(0, N);
for (int n = 1; n <= (N+1)/2; n++) {
ll v = +INF;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
if (int(res[a][b].size()) > n) {
setmin(v, res[a][b][n]);
}
}
}
cout << v << '\n';
}
return 0;
}