Untitled

#include <iostream>
#include <vector>
using namespace std;
 
typedef long double ld;
typedef long long ll;
 
ll gcd(ll a, ll b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}
 
struct Fraction {
    ll a, b;
 
    Fraction(ll a, ll b) {
        this->a = a;
        this->b = b;
    }
 
    Fraction operator-(Fraction other) {
        ll x = a * other.b - other.a * b;
        ll y = b * other.b;
        ll g = gcd(abs(x), abs(y));
        return { x / g, y / g };
    }
 
    bool operator<=(Fraction other) {
        Fraction res = other - (*this);
        return res.a >= 0;
    }
 
    bool operator<(Fraction other) const {
        Fraction res = other - (*this);
        return res.a > 0;
    }
};
 
int main() {
    cout.precision(20);
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> pref_min(n), pref_max(n), suff_min(n), suff_max(n);
    for (int& i : arr) cin >> i;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            pref_min[i] = arr[i];
            pref_max[i] = arr[i];
        }
        else {
            pref_min[i] = min(pref_min[i - 1], arr[i]);
            pref_max[i] = max(pref_max[i - 1], arr[i]);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) {
            suff_min[i] = arr[i];
            suff_max[i] = arr[i];
        }
        else {
            suff_min[i] = min(arr[i], suff_min[i + 1]);
            suff_max[i] = max(arr[i], suff_max[i + 1]);
        }
    }
 
    vector<pair<Fraction, ld>> answer(n + 1, { Fraction(1e18, 1), 0 });
    for (int k = 1; k <= n; k++) {
        if (k == n) {
            answer[k] = { Fraction(0, 1), 1 };
        }
        else {
            ll pmin = pref_min[n - k - 1];
            ll pmax = pref_max[n - k - 1];
            ll smin = suff_min[n - k];
            ll smax = suff_max[n - k];
 
            // first case pmax and pmin
            Fraction left_border = max(Fraction(0, 1), Fraction(1, 1) - Fraction(pmax, smax));
            Fraction right_border = Fraction(1, 1) - Fraction(pmin, smin);
 
            if (left_border <= right_border) {
                if (Fraction(pmax - pmin, 1) <= answer[k].first) {
                    answer[k].first = Fraction(pmax - pmin, 1);
                    answer[k].second = ((ld)right_border.a) / right_border.b;
                }
            }
 
            // second case pmax and smin
            left_border = max(Fraction(1, 1) - Fraction(pmin, smin), Fraction(1, 1) - Fraction(pmax, smax));
            left_border = max(Fraction(0, 1), left_border);
 
            if (left_border <= Fraction(1, 1)) {
                left_border.a *= smin;
                Fraction res = Fraction(pmax, 1) - left_border;
                if (res <= answer[k].first) {
                    answer[k].first = res;
                    left_border.a /= smin;
                    answer[k].second = ((ld)left_border.a) / left_border.b;
                }
            }
 
            // third case smax and pmin
            right_border = min(Fraction(1, 1) - Fraction(pmax, smax), Fraction(1, 1) - Fraction(pmin, smin));
            if (Fraction(0, 1) <= right_border) {
                Fraction tmp = (Fraction(1, 1) - right_border);
                tmp.a *= smax;
                Fraction res = tmp - Fraction(pmin, 1);
                if (res <= answer[k].first) {
                    answer[k].first = res;
                    answer[k].second = ((ld)right_border.a) / right_border.b;
                }
            }
 
            // fourth case smax and smin
            right_border = Fraction(1, 1) - Fraction(pmax, smax);
            left_border = max(Fraction(0, 1), Fraction(1, 1) - Fraction(pmin, smin));
            if (left_border <= right_border) {
                Fraction tmp1 = Fraction(1, 1) - right_border;
                tmp1.a *= smax;
                Fraction tmp2 = Fraction(1, 1) - right_border;
                tmp2.a *= smin;
                Fraction res = tmp1 - tmp2;
                if (res <= answer[k].first) {
                    answer[k].first = res;
                    answer[k].second = ((ld)right_border.a) / right_border.b;
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        cout << answer[n - i + 1].second << ' ';
    }
    cout << '\n';
}