Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % mod; }
int sub(int x, int y) { return (x - y + mod) % mod; }
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int modpow(int n, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = mul(res, n);
        n = mul(n, n);
        k >>= 1;
    }
    return res;
}
int divide(int a, int b) { return mul(a, modpow(b, mod - 2)); }

struct fenwick_point {
    int n;
    vector<int> fenw;
    fenwick_point(int _n) : n(_n + 5) { fenw.resize(n); }

    void increment(int i, int v) {
        for (++i; i < n; i += (i & -i)) fenw[i] = add(fenw[i], v);
    }
    int query(int i) {
        int res = 0;
        for (++i; i > 0; i -= (i & -i)) res = add(res, fenw[i]);
        return res;
    }
};


void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll& u : a) cin >> u;

    auto modulo = [&](ll x) {
        while (x < 0) x += (ll)mod;
        return x % mod;
    };

    map<ll, int> comp;
    for (ll u : a) comp[u];
    int id = 1;
    for (auto& u : comp) u.second = id++;

    fenwick_point freq(n + 1);
    fenwick_point sum(n + 5);

    vector<int> p2(n + 5), invp2(n + 5);
    p2[0] = invp2[0] = 1;
    p2[1] = 2;
    invp2[1] = divide(1, 2);
    for (int i = 2; i <= n + 4; i++) {
        p2[i] = mul(p2[i - 1], p2[1]);
        invp2[i] = mul(invp2[i - 1], invp2[1]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        int j = comp[a[i]];

        // (a[i] - a[before]) * 2^{before - 1} * 2^{n - i - 1}
        res = add(res, mul(mul(modulo(a[i]), freq.query(j - 1)), p2[n - i - 1]));
        res = sub(res, mul(sum.query(j - 1), p2[n - i - 1]));

        // (a[before] - a[i]) * 2^{before - 1} * 2^{n - i - 1}
        res = add(res, mul(sub(sum.query(n + 3), sum.query(j - 1)), p2[n - i - 1]));
        res = sub(res, mul(mul(modulo(a[i]), p2[n - i - 1]), sub(freq.query(n + 3), freq.query(j - 1))));

        freq.increment(j, p2[i]);
        sum.increment(j, mul(p2[i], modulo(a[i])));
    }

    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    tt = 1, tc = 1; // cin >> tt;
    while (tt--) solve(), tc++;
}