Problem: There are n officers in the Army of Byteland. Each officer has some power associated with him. The power of the i-th officer is denoted by p_{i}. As the war is fast approaching, the General would like to know the strength of the army.

The strength of an army is calculated in a strange way in Byteland. The General selects a random subset of officers from these n officers and calls this subset a battalion.(All 2^n subsets of the n officers can be chosen equally likely, including empty subset and the subset of all officers).

The strength of a battalion is calculated in the following way:

Let the powers of the chosen officers be a_{1},a_{2},…,a_{k}, where a_1 ≤ a_2 ≤ ... ≤ a_k. The strength of this battalion is equal to a_1a_2 + a_2a_3 + ... + a_{k-1}a_k. (If the size of Battalion is ≤ 1, then the strength of this battalion is 0).

The strength of the army is equal to the expected value of the strength of the battalion.

As the war is really long, the powers of officers may change. Precisely, there will be q changes. Each one of the form i x indicating that p_{i} is changed to x.

You need to find the strength of the army initially and after each of these q updates.

Note that the changes are permanent.

The strength should be found by modulo 10^{9}+7. Formally, let M=10^{9}+7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and qnot≡ 0 mod M). Output the integer equal to p⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p mod M).

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 3⋅10^{5}) — the number of officers in Byteland's Army.

The second line contains n integers p_{1},p_{2},…,p_{n} (1 ≤ p_{i} ≤ 10^{9}).

The third line contains a single integer q (1 ≤ q ≤ 3⋅10^{5}) — the number of updates.

Each of the next q lines contains two integers i and x (1 ≤ i ≤ n,  1 ≤ x ≤ 10^{9}), indicating that p_{i} is updated to x .

Output

In the first line output the initial strength of the army.

In i-th of the next q lines, output the strength of the army after i-th update.

Examples

Input


2
1 2
2
1 2
2 1


Output


500000004
1
500000004


Input


4
1 2 3 4
4
1 5
2 5
3 5
4 5


Output


625000011
13
62500020
375000027
62500027

Note

In first testcase, initially, there are four possible battalions 

  * {} Strength = 0 
  * {1} Strength = 0 
  * {2} Strength = 0 
  * {1,2} Strength = 2 

So strength of army is (0+0+0+2)/(4) = 1/2

After changing p_{1} to 2, strength of battallion {1,2} changes to 4, so strength of army becomes 1.

After changing p_{2} to 1, strength of battalion {1,2} again becomes 2, so strength of army becomes 1/2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long nega[300020];
long long posi[300020];
struct seg_addsum_getsum {
 private:
 public:
  long long cor = (1 << 20);
  vector<long long> vec;
  vector<long long> lazy;
  vector<long long> hoge;
  void shoki1() {
    vec.resize(2 * cor + 3, 0);
    lazy.resize(2 * cor + 3, 0);
    hoge.resize(2 * cor + 3, 0);
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--)
      vec[i] = (vec[2 * i] + vec[2 * i + 1]) % mod;
    for (long long i = cor - 1; i > 0; i--)
      hoge[i] = (hoge[2 * i] + hoge[2 * i + 1]);
  }
  void chien(long long k, long long l, long long r) {
    if (lazy[k] == 0) return;
    if (l + 1 < r) {
      lazy[k * 2] += lazy[k];
      lazy[k * 2 + 1] += lazy[k];
    }
    if (lazy[k] > 0) vec[k] *= posi[lazy[k]];
    if (lazy[k] < 0) vec[k] *= nega[-lazy[k]];
    vec[k] %= mod;
    lazy[k] = 0;
  }
  void rangeadd(long long a, long long b, long long w, long long k = 1,
                long long l = 0, long long r = -3) {
    if (r < 0) r = cor;
    chien(k, l, r);
    if (a <= l && r <= b) {
      lazy[k] += w;
      chien(k, l, r);
      return;
    }
    if (r <= a || b <= l) {
      return;
    }
    rangeadd(a, b, w, k * 2, l, (l + r) / 2);
    rangeadd(a, b, w, k * 2 + 1, (l + r) / 2, r);
    vec[k] = (vec[2 * k] + vec[2 * k + 1]) % mod;
    return;
  }
  void makezero(long long p, bool bo, long long k = 1, long long l = 0,
                long long r = -3) {
    if (r < 0) r = cor;
    while (1) {
      chien(k, l, r);
      long long me = (l + r) / 2;
      if (r - l == 1) break;
      if (p < me) {
        r = me;
        k *= 2;
      } else {
        l = me;
        k = k * 2 + 1;
      }
    }
    long long d = vec[k];
    while (k) {
      if (bo) hoge[k]--;
      vec[k] += mod - d;
      vec[k] %= mod;
      k /= 2;
    }
  }
  void pointadd(long long p, long long w, long long k = 1, long long l = 0,
                long long r = -3) {
    if (r < 0) r = cor;
    while (1) {
      chien(k, l, r);
      long long me = (l + r) / 2;
      vec[k] += w;
      vec[k] %= mod;
      hoge[k]++;
      if (r - l == 1) break;
      if (p < me) {
        r = me;
        k *= 2;
      } else {
        l = me;
        k = k * 2 + 1;
      }
    }
    return;
  }
  long long getsum(long long a, long long b, long long k = 1, long long l = 0,
                   long long r = -3) {
    if (r < 0) r = cor;
    chien(k, l, r);
    if (a <= l && r <= b) {
      return vec[k];
    }
    if (r <= a || b <= l) {
      return 0;
    }
    return (getsum(a, b, k * 2, l, (l + r) / 2) +
            getsum(a, b, k * 2 + 1, (l + r) / 2, r)) %
           mod;
  }
  long long getiti(long long a, long long b, long long k = 1, long long l = 0,
                   long long r = -3) {
    if (r < 0) r = cor;
    if (a <= l && r <= b) {
      return hoge[k];
    }
    if (r <= a || b <= l) {
      return 0;
    }
    return getiti(a, b, k * 2, l, (l + r) / 2) +
           getiti(a, b, k * 2 + 1, (l + r) / 2, r);
  }
  void pre() {
    for (long long i = 1; i < 2 * cor; i++) {
      cout << vec[i] << "/" << lazy[i] << " ";
      if (((i + 1) & (-(i + 1))) == i + 1) cout << endl;
    }
  }
};
long long be[300020];
long long iti[300020];
long long atai[300020];
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  mod = 1000000007;
  posi[0] = 1;
  nega[0] = 1;
  long long ni = beki(2, mod - 2, mod);
  for (long long i = 1; i <= 300010; i++) {
    posi[i] = posi[i - 1] * 2 % mod;
    nega[i] = nega[i - 1] * ni % mod;
  }
  vector<long long> ve(n + 1);
  vector<pair<long long, long long> > zen;
  for (long long i = 1; i <= n; i++) {
    long long y;
    cin >> y;
    ve[i] = y;
    zen.push_back(make_pair(y, -i));
  }
  vector<pa3> query;
  long long Q;
  cin >> Q;
  query.push_back({0, 0, 0});
  for (long long i = 1; i <= Q; i++) {
    long long x, y;
    cin >> x >> y;
    query.push_back({x, y, 0});
    zen.push_back(make_pair(y, i));
  }
  sort(zen.begin(), zen.end());
  seg_addsum_getsum ss1, ss2;
  ss1.shoki1();
  ss2.shoki1();
  vector<pair<long long, long long> > f;
  for (long long i = 0; i < zen.size(); i++) {
    if (zen[i].second < 0) {
      ss1.vec[ss1.cor + i + 1] = zen[i].first;
      ss2.vec[ss2.cor + i + 1] = zen[i].first;
      ss1.hoge[ss1.cor + i + 1] = 1;
      iti[-zen[i].second] = i + 1;
      atai[-zen[i].second] = zen[i].first;
      f.push_back(make_pair(i + 1, zen[i].first));
    } else {
      query[zen[i].second].z = i + 1;
    }
  }
  long long cnt = 1;
  for (long long i = 0; i < ss1.cor; i++)
    if (ss1.hoge[ss1.cor + i]) {
      ss1.vec[ss1.cor + i] *= nega[cnt];
      ss2.vec[ss1.cor + i] *= nega[n + 1 - cnt];
      ss1.vec[ss1.cor + i] %= mod;
      ss2.vec[ss1.cor + i] %= mod;
      cnt++;
    }
  ss1.shoki2();
  ss2.shoki2();
  long long ans = 0;
  sort(f.begin(), f.end());
  for (long long i = 0; i < n; i++) {
    ans +=
        f[i].second * ss1.getsum(f[i].first + 1, ss1.cor) % mod * posi[i] % mod;
  }
  ans %= mod;
  cout << ans << endl;
  for (long long q = 1; q <= Q; q++) {
    long long it = iti[query[q].x];
    long long p = ss1.getiti(0, it + 1);
    long long t1 = ss1.getsum(it + 1, ss1.cor);
    long long t2 = ss2.getsum(0, it);
    long long mae = t1 * posi[p - 1] % mod;
    mae += t2 * posi[n - p] % mod;
    mae %= mod;
    mae *= atai[query[q].x];
    mae += mod - t1 * t2 % mod * posi[n] % mod;
    mae %= mod;
    ss1.makezero(it, 1);
    ss2.makezero(it, 1);
    ss1.rangeadd(it, ss1.cor, 1);
    ss2.rangeadd(0, it, 1);
    atai[query[q].x] = query[q].y;
    iti[query[q].x] = query[q].z;
    it = iti[query[q].x];
    p = ss1.getiti(0, it);
    ss1.pointadd(it, query[q].y * nega[p] % mod);
    ss2.pointadd(it, query[q].y * nega[n - 1 - p] % mod);
    ss1.rangeadd(it, ss1.cor, -1);
    ss2.rangeadd(0, it + 1, -1);
    p++;
    t1 = ss1.getsum(it + 1, ss1.cor);
    t2 = ss2.getsum(0, it);
    long long ato = t1 * posi[p - 1] % mod;
    ato += t2 * posi[n - p] % mod;
    ato %= mod;
    ato *= atai[query[q].x];
    ato %= mod;
    ato += mod - posi[n] * t1 % mod * t2 % mod;
    ato %= mod;
    ans += mod - mae + ato;
    ans %= mod;
    cout << "" << ans << "\n";
  }
  return 0;
}