#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define rep(i, n) for (int i = 0; i < n; i++) #define per(i, n) for (int i = n - 1; i >= 0; i--) #define Rep(i, sta, n) for (int i = sta; i < n; i++) #define Per(i, sta, n) for (int i = n - 1; i >= sta; i--) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1}; template using max_heap = priority_queue; template using min_heap = priority_queue, greater<>>; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template struct ModInt { long long x; static constexpr int MOD = mod; ModInt() : x(0) {} ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} explicit operator int() const { return x; } ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator%(const ModInt &p) const { return ModInt(0); } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } ModInt power(long long n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } ModInt power(const ModInt p) const { return ((ModInt)x).power(p.x); } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { long long x; is >> x; a = ModInt(x); return (is); } }; using modint = ModInt; template struct SegmentTree { public: SegmentTree() : SegmentTree(0) {} SegmentTree(int n) : SegmentTree(std::vector(n, e())) {} SegmentTree(const std::vector &v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set_val(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S query(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_query() { return d[1]; } template int max_right(int l) { // f(op([l,r)))==trueを満たす最大のr return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { // f(op([l,r)))==trueを満たす最小のl return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } }; template struct Compress { vector V; Compress() { V.clear(); } Compress(vector &V) : V(V) {} void add(T x) { V.push_back(x); } int build() { sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end()); return V.size(); } int get(T x) { // get the index of the minimum element which is greater than // x return lower_bound(V.begin(), V.end(), x) - V.begin(); } pair section(T l, T r) { // get the range of indexes of [l,r) int l_ = get(l), r_ = get(r); return pair(l_, r_); } T &operator[](int i) { return V[i]; }; }; int n, a[200010]; modint pow2[200010]; vector v[200010]; modint F(modint a, modint b) { return a + b; } modint e() { return 0; } void solve() { cin >> n; Compress comp; rep(i, n) { cin >> a[i]; comp.add(a[i]); } pow2[0] = 1; rep(i, n) pow2[i + 1] = pow2[i] * 2; int m = comp.build(); rep(i, n) v[comp.get(a[i])].push_back(i); SegmentTree seg1(n), seg2(n), seg3(n), seg4(n); modint ans = 0; rep(i, m) { for (int t : v[i]) { ans += seg1.query(0, t) * seg2.query(t + 1, n); } for (int t : v[i]) { seg1.set_val(t, pow2[t]); seg2.set_val(t, pow2[n - 1 - t]); } } per(i, m) { for (int t : v[i]) { ans += seg3.query(0, t) * seg4.query(t + 1, n); } for (int t : v[i]) { seg3.set_val(t, pow2[t]); seg4.set_val(t, pow2[n - 1 - t]); } } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }