// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define sz(x) int(x.size()) template<class T> using V = vector<T>; using vi = V<int>; const int MOD = 1e9 + 7; int add(int x, int y) { x += y; if (x >= MOD) x -= MOD; return x; } int sub(int x, int y) { x -= y; if (x < 0) x += MOD; return x; } void sadd(int &x, int y) { x = add(x, y); } int mul(int x, int y) { return (x * 1LL * y) % MOD; } void smul(int &x, int y) { x = mul(x, y); } struct T { int ans = 0, ways = 0, xways = 0, pos = 0; }; const T ID = {0, 0, 0, 0}; const int nax = (1 << 20); T seg[2 * nax]; int pw2[nax], lzy[2 * nax]; T cmb(T a, T b) { sadd(a.ans, b.ans); sadd(a.ways, b.ways); sadd(a.xways, b.xways); sadd(a.pos, b.pos); return a; } void pull(int x) { seg[x] = cmb(seg[2 * x], seg[2 * x + 1]); } void push(int x, int L, int R) { if (lzy[x] != 1) { smul(seg[x].ans, lzy[x]); smul(seg[x].ways, lzy[x]); smul(seg[x].xways, lzy[x]); smul(seg[x].pos, lzy[x]); } if (L != R && lzy[x] != 1) for(int i = 0; i < 2; i++) smul(lzy[2 * x + i], lzy[x]); lzy[x] = 1; } void upd(int l, int r, int v, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (r < L || R < l) return; if (l <= L && R <= r) { lzy[x] = v; push(x, L, R); return; } int M = (L + R) / 2; upd(l, r, v, 2 * x, L, M); upd(l, r, v, 2 * x + 1, M + 1, R); pull(x); } void upd(int p, T v, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (p < L || R < p) return; if (L == R) { seg[x] = v; return; } int M = (L + R) / 2; upd(p, v, 2 * x, L, M); upd(p, v, 2 * x + 1, M + 1, R); pull(x); } T qry(int l, int r, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (r < L || R < l) return ID; if (l <= L && R <= r) { return seg[x]; } int M = (L + R) / 2; return cmb(qry(l, r, 2 * x, L, M), qry(l, r, 2 * x + 1, M + 1, R)); } int main() { cin.tie(0)->sync_with_stdio(0); pw2[0] = 1; for(int i = 1; i < nax; i++) pw2[i] = mul(pw2[i - 1], 2); int N; cin >> N; vi A(N); for(auto& x : A) cin >> x; vi B(N); for(auto& x : B) cin >> x; vi X = {0}; X.insert(end(X), begin(A), end(A)); X.insert(end(X), begin(B), end(B)); sort(begin(X), end(X)); X.erase(unique(begin(X), end(X)), end(X)); int M = sz(X); for(auto& x : A) x = lower_bound(begin(X), end(X), x) - begin(X); for(auto& x : B) x = lower_bound(begin(X), end(X), x) - begin(X); map<array<int, 2>, array<int, 2>> L, R; for(int t = 0; t <= 1; ++t) { for(int i = 0; i < 2 * nax; i++) { seg[i] = T{0, 0, 0, 0}; lzy[i] = 1; } upd(0, T{0, 1, 0, 0}); for(int i = 0; i < N; i++) { // cout << qry(0, M - 1).ways << endl; T qa = qry(0, A[i] - t), qb = qry(0, B[i] - t); sadd(qa.ans, sub(mul(qa.xways, i), qa.pos)); sadd(qb.ans, sub(mul(qb.xways, i), qb.pos)); L[{A[i], i}] = {qa.ans, qa.ways}; L[{B[i], i}] = {qb.ans, qb.ways}; // cout << A[i] << " " << i << " -> " << qa.ans << " " << qa.ways << endl; // cout << B[i] << " " << i << " -> " << qb.ans << " " << qb.ways << endl; T lessa = qry(0, A[i]), lessb = qry(0, B[i]); int mn = min(A[i], B[i]), mx = max(A[i], B[i]); upd(0, mn, 0); // x < a, x < b -> cant be max upd(mx + 1, M - 1, 2); // x < a, x < b -> both keep this as the max T ata = qry(A[i], A[i]), atb = qry(B[i], B[i]); { int amt = lessa.ways; sadd(ata.ways, amt); smul(amt, X[A[i]]); sadd(ata.xways, amt); smul(amt, i); sadd(ata.pos, amt); sadd(ata.ans, sub(mul(lessa.xways, i), lessa.pos)); sadd(ata.ans, lessa.ans); upd(A[i], ata); // cout << A[i] << " " << i << " -> " << ata.ans << " " << ata.ways << endl; } { int amt = lessb.ways; sadd(atb.ways, amt); smul(amt, X[B[i]]); sadd(atb.xways, amt); smul(amt, i); sadd(atb.pos, amt); sadd(atb.ans, sub(mul(lessb.xways, i), lessb.pos)); sadd(atb.ans, lessb.ans); upd(B[i], atb); // cout << B[i] << " " << i << " -> " << atb.ans << " " << atb.ways << endl; } } L.swap(R); reverse(begin(A), end(A)); reverse(begin(B), end(B)); } int ans = 0; for(int i = 0; i < N; i++) { sadd(ans, mul(MOD - A[i], pw2[N - 1])); sadd(ans, mul(MOD - B[i], pw2[N - 1])); } // cout << "SUB: " << ans << nl; int tot = 0; for(auto& [p, v] : L) { auto [x, i] = p; auto [lv, lways] = v; auto [rv, rways] = R[{x, N - 1 - i}]; // cout << x << " -> " << X[x] << " " << i << " ==> " << lv << " " << lways << " " << rv << " " << rways << endl; sadd(tot, mul(lways, rways)); sadd(ans, mul(rv, lways)); sadd(ans, mul(lv, rways)); sadd(ans, mul(mul(lways, rways), X[x])); } assert(tot == pw2[N]); cout << ans << nl; exit(0-0); } // Breathe In, Breathe Out