Problem: On the 228-th international Uzhlyandian Wars strategic game tournament teams from each country are called. The teams should consist of 5 participants.

The team of Uzhlyandia will consist of soldiers, because there are no gamers.

Masha is a new minister of defense and gaming. The prime duty of the minister is to calculate the efficiency of the Uzhlandian army. The army consists of n soldiers standing in a row, enumerated from 1 to n. For each soldier we know his skill in Uzhlyandian Wars: the i-th soldier's skill is ai.

It was decided that the team will consist of three players and two assistants. The skills of players should be same, and the assistants' skills should not be greater than the players' skill. Moreover, it is important for Masha that one of the assistants should stand in the row to the left of the players, and the other one should stand in the row to the right of the players. Formally, a team is five soldiers with indexes i, j, k, l, p, such that 1 ≤ i < j < k < l < p ≤ n and ai ≤ aj = ak = al ≥ ap. 

The efficiency of the army is the number of different teams Masha can choose. Two teams are considered different if there is such i such that the i-th soldier is a member of one team, but not a member of the other team.

Initially, all players are able to be players. For some reasons, sometimes some soldiers become unable to be players. Sometimes some soldiers, that were unable to be players, become able to be players. At any time any soldier is able to be an assistant. Masha wants to control the efficiency of the army, so she asked you to tell her the number of different possible teams modulo 1000000007 (109 + 7) after each change. 

Input

The first line contains single integer n (1 ≤ n ≤ 105) — the number of soldiers in Uzhlyandia.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the soldiers' skills.

The third line contains single integer m (1 ≤ m ≤ 105) — the number of changes.

The next m lines contain the changes, each change is described with two integers t and x (1 ≤ t ≤ 2, 1 ≤ x ≤ n) on a separate line. If t = 1, then the x-th soldier is unable to be a player after this change. If t = 2, then the x-th soldier is able to be a player after this change. 

It is guaranteed that before each query of the first type the soldier is able to be a player, and before each query of the second type the soldier is unable to be a player.

Output

Print m integers — the number of distinct teams after each change.

Print the answers modulo 1000000007 (109 + 7). 

Examples

Input

6
1 1 1 1 1 1
2
1 3
2 3


Output

1
6


Input

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


Output

1
6
2

Note

In the first example, after the first change the only team consists of soldiers [1, 2, 4, 5, 6]. After the second change any five soldiers can form a team.

In the first example after the first change the only team is soldiers [1, 2, 3, 7, 8]. After the second change the possible teams are: [1, 2, 3, 5, 7], [1, 2, 3, 5, 8], [1, 2, 3, 7, 8], [1, 2, 5, 7, 8], [1, 3, 5, 7, 8], [2, 3, 5, 7, 8]. After the third change the possible teams are: [1, 3, 5, 7, 8], [2, 3, 5, 7, 8].

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
vector<int> dataidx[int(1e5 + 1000)], diff;
vector<long long int> prefix_seg[int(1e5 + 1000)],
    prefix_layer[int(1e5 + 1000)], suffix_seg[int(1e5 + 1000)],
    suffix_layer[int(1e5 + 1000)], active[int(1e5 + 1000)],
    prefix_sum_seg[int(1e5 + 1000)], suffix_sum_seg[int(1e5 + 1000)],
    pre[int(1e5 + 1000)], suf[int(1e5 + 1000)], en[int(1e5 + 1000)],
    pre_sum[int(1e5 + 1000)], suf_sum[int(1e5 + 1000)];
int seg[4 * int(1e5 + 1000)] = {0}, MaxVal = 1e5, pos[int(1e5 + 1000)],
                      tree[int(1e5 + 1000)] = {0}, a[int(1e5 + 1000)];
map<int, int> Rank;
bool uu = 0;
int read(int idx) {
  int sum = 0;
  while (idx > 0) {
    sum += tree[idx];
    idx -= (idx & -idx);
  }
  return sum;
}
void update(int idx, int val) {
  while (idx <= MaxVal) {
    tree[idx] += val;
    idx += (idx & -idx);
  }
}
void insert(int node, int it, int f, int id) {
  if (it == f) {
    prefix_seg[id][node] = pre[id][f - 1];
    suffix_seg[id][node] = suf[id][f - 1];
    prefix_sum_seg[id][node] = pre_sum[id][f - 1];
    suffix_sum_seg[id][node] = suf_sum[id][f - 1];
    active[id][node] = 1;
    return;
  }
  int m = (it + f) / 2, ln = node * 2, rn;
  rn = ln + 1;
  insert(ln, it, m, id);
  insert(rn, m + 1, f, id);
  active[id][node] = f - it + 1;
  prefix_seg[id][node] =
      (prefix_seg[id][ln] + prefix_seg[id][rn]) % int(1e9 + 7);
  prefix_sum_seg[id][node] =
      (prefix_sum_seg[id][ln] + prefix_sum_seg[id][rn]) % int(1e9 + 7);
  suffix_seg[id][node] =
      (suffix_seg[id][ln] + suffix_seg[id][rn]) % int(1e9 + 7);
  suffix_sum_seg[id][node] =
      (suffix_sum_seg[id][ln] + suffix_sum_seg[id][rn]) % int(1e9 + 7);
}
void point_update(int node, int it, int f, int q, bool enable, int id) {
  if (it == f) {
    if (!enable) {
      prefix_seg[id][node] = 0;
      suffix_seg[id][node] = 0;
      prefix_sum_seg[id][node] = 0;
      suffix_sum_seg[id][node] = 0;
      active[id][node]--;
    } else {
      prefix_seg[id][node] = pre[id][f - 1];
      suffix_seg[id][node] = suf[id][f - 1];
      prefix_sum_seg[id][node] =
          (pre_sum[id][f - 1] + prefix_layer[id][node]) % int(1e9 + 7);
      suffix_sum_seg[id][node] =
          (suf_sum[id][f - 1] + suffix_layer[id][node]) % int(1e9 + 7);
      active[id][node]++;
    }
    return;
  }
  int m = (it + f) / 2;
  if (q <= m)
    point_update(node * 2, it, m, q, enable, id);
  else
    point_update(node * 2 + 1, m + 1, f, q, enable, id);
  if (enable)
    active[id][node]++;
  else
    active[id][node]--;
  prefix_seg[id][node] =
      (prefix_seg[id][node * 2] + prefix_seg[id][node * 2 + 1]) % int(1e9 + 7);
  suffix_seg[id][node] =
      (suffix_seg[id][node * 2] + suffix_seg[id][node * 2 + 1]) % int(1e9 + 7);
  prefix_sum_seg[id][node] =
      (prefix_sum_seg[id][node * 2] + prefix_sum_seg[id][node * 2 + 1] +
       active[id][node] * prefix_layer[id][node]) %
      int(1e9 + 7);
  suffix_sum_seg[id][node] =
      (suffix_sum_seg[id][node * 2] + suffix_sum_seg[id][node * 2 + 1] +
       active[id][node] * suffix_layer[id][node]) %
      int(1e9 + 7);
}
void range_update_prefix(int node, int it, int f, int q, int id,
                         long long int val, bool enable) {
  if (q == it) {
    if (enable) {
      prefix_sum_seg[id][node] =
          (prefix_sum_seg[id][node] + active[id][node] * val) % int(1e9 + 7);
      prefix_layer[id][node] = (prefix_layer[id][node] + val) % int(1e9 + 7);
    } else {
      prefix_sum_seg[id][node] =
          (prefix_sum_seg[id][node] - active[id][node] * val) % int(1e9 + 7);
      prefix_layer[id][node] = (prefix_layer[id][node] - val) % int(1e9 + 7);
    }
    return;
  }
  int m = (it + f) / 2, ln = node * 2, rn;
  rn = ln + 1;
  if (q > m) {
    range_update_prefix(rn, m + 1, f, q, id, val, enable);
  } else {
    range_update_prefix(ln, it, m, q, id, val, enable);
    range_update_prefix(rn, m + 1, f, m + 1, id, val, enable);
  }
  prefix_sum_seg[id][node] = (prefix_sum_seg[id][ln] + prefix_sum_seg[id][rn] +
                              active[id][node] * prefix_layer[id][node]) %
                             int(1e9 + 7);
}
void range_update_suffix(int node, int it, int f, int q, int id,
                         long long int val, bool enable) {
  if (q == f) {
    if (enable) {
      suffix_sum_seg[id][node] =
          (suffix_sum_seg[id][node] + active[id][node] * val) % int(1e9 + 7);
      suffix_layer[id][node] = (suffix_layer[id][node] + val) % int(1e9 + 7);
    } else {
      suffix_sum_seg[id][node] =
          (suffix_sum_seg[id][node] - active[id][node] * val) % int(1e9 + 7);
      suffix_layer[id][node] = (suffix_layer[id][node] - val) % int(1e9 + 7);
    }
    return;
  }
  int m = (it + f) / 2, ln = node * 2, rn;
  rn = ln + 1;
  if (q <= m)
    range_update_suffix(ln, it, m, q, id, val, enable);
  else {
    range_update_suffix(ln, it, m, m, id, val, enable);
    range_update_suffix(rn, m + 1, f, q, id, val, enable);
  }
  suffix_sum_seg[id][node] = (suffix_sum_seg[id][ln] + suffix_sum_seg[id][rn] +
                              active[id][node] * suffix_layer[id][node]) %
                             int(1e9 + 7);
}
long long int get_prefix(int node, int it, int f, int q, int id) {
  if (q == f) return prefix_seg[id][node] % int(1e9 + 7);
  int m = (it + f) / 2;
  if (q <= m)
    return get_prefix(node * 2, it, m, q, id);
  else
    return (prefix_seg[id][node * 2] +
            get_prefix(node * 2 + 1, m + 1, f, q, id)) %
           int(1e9 + 7);
}
long long int get_prefix_sum(int node, int it, int f, int q, int id,
                             long long int upperL) {
  if (q == f)
    return (prefix_sum_seg[id][node] + active[id][node] * upperL) %
           int(1e9 + 7);
  upperL += prefix_layer[id][node];
  int m = (it + f) / 2;
  if (q <= m)
    return get_prefix_sum(node * 2, it, m, q, id, upperL % int(1e9 + 7));
  else {
    int val = get_prefix_sum(node * 2, it, m, m, id, upperL % int(1e9 + 7));
    return val +
           get_prefix_sum(node * 2 + 1, m + 1, f, q, id, upperL % int(1e9 + 7));
  }
}
long long int get_suffix(int node, int it, int f, int q, int id) {
  if (q == it) return suffix_seg[id][node] % int(1e9 + 7);
  int m = (it + f) / 2;
  if (q > m)
    return get_suffix(node * 2 + 1, m + 1, f, q, id);
  else
    return (suffix_seg[id][node * 2 + 1] + get_suffix(node * 2, it, m, q, id)) %
           int(1e9 + 7);
}
long long int get_suffix_sum(int node, int it, int f, int q, int id,
                             long long int upperL) {
  if (q == it) {
    return (suffix_sum_seg[id][node] + active[id][node] * upperL) %
           int(1e9 + 7);
  }
  upperL += suffix_layer[id][node];
  int m = (it + f) / 2;
  if (q > m) {
    return get_suffix_sum(node * 2 + 1, m + 1, f, q, id, upperL % int(1e9 + 7));
  } else {
    long long int val = get_suffix_sum(node * 2 + 1, m + 1, f, m + 1, id,
                                       upperL % int(1e9 + 7));
    return (val +
            get_suffix_sum(node * 2, it, m, q, id, upperL % int(1e9 + 7))) %
           int(1e9 + 7);
  }
}
int get_prv(int node, int it, int f, int q, int id) {
  if (!active[id][node]) return -1;
  if (it == f) {
    return f;
  }
  int m = (it + f) / 2;
  int idx = -1;
  if (q > m) {
    idx = get_prv(node * 2 + 1, m + 1, f, q, id);
    if (idx != -1) return idx;
    return get_prv(node * 2, it, m, m, id);
  }
  return get_prv(node * 2, it, m, q, id);
}
int get_nxt(int node, int it, int f, int q, int id) {
  if (!active[id][node]) return -1;
  if (it == f) {
    return f;
  }
  int m = (it + f) / 2;
  int idx = -1;
  if (q <= m) {
    idx = get_nxt(node * 2, it, m, q, id);
    if (idx != -1) return idx;
    return get_nxt(node * 2 + 1, m + 1, f, m + 1, id);
  }
  return get_nxt(node * 2 + 1, m + 1, f, q, id);
}
int main() {
  int n;
  scanf("%d", &n);
  ;
  for (int i = int(1); i <= (int)n; i++) {
    scanf("%d", &a[i]);
    ;
    diff.push_back(a[i]);
  }
  sort(diff.begin(), diff.end());
  int idx = 0;
  for (int i = 1; i < n; ++i) {
    if (diff[i] != diff[i - 1]) diff[++idx] = diff[i];
  }
  for (int i = 0; i <= idx; ++i) Rank[diff[i]] = i + 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = Rank[a[i]];
    dataidx[a[i]].push_back(i);
    pos[i] = (int)dataidx[a[i]].size();
  }
  for (int i = 1; i <= idx + 1; ++i) {
    int szz = (int)dataidx[i].size();
    prefix_seg[i].resize(4 * szz);
    suffix_seg[i].resize(4 * szz);
    prefix_sum_seg[i].resize(4 * szz);
    suffix_sum_seg[i].resize(4 * szz);
    prefix_layer[i].resize(4 * szz);
    suffix_layer[i].resize(4 * szz);
    active[i].resize(4 * szz);
    pre[i].resize(szz + 5);
    suf[i].resize(szz + 5);
    pre_sum[i].resize(szz + 5);
    suf_sum[i].resize(szz + 5);
    fill(prefix_seg[i].begin(), prefix_seg[i].end(), +0);
    fill(suffix_seg[i].begin(), suffix_seg[i].end(), +0);
    fill(prefix_sum_seg[i].begin(), prefix_sum_seg[i].end(), +0);
    fill(suffix_sum_seg[i].begin(), suffix_sum_seg[i].end(), +0);
    fill(prefix_layer[i].begin(), prefix_layer[i].end(), +0);
    fill(suffix_layer[i].begin(), suffix_layer[i].end(), +0);
  }
  int tot = 0, id;
  for (int i = 1; i <= idx + 1; ++i) {
    int szz = (int)dataidx[i].size();
    long long int pre_s = 0, suf_s = 0;
    tot += szz;
    for (int j = 0; j < szz; ++j) {
      id = dataidx[i][j];
      update(id, +1);
    }
    for (int j = 0; j < szz; ++j) {
      pre[i][j] = (read(dataidx[i][j]) - 1) % int(1e9 + 7);
      pre_s += pre[i][j];
      pre_sum[i][j] = pre_s % int(1e9 + 7);
      suf[i][j] = (tot - pre[i][j] - 1) % int(1e9 + 7);
    }
    for (int j = szz - 1; j >= 0; j--) {
      suf_s += suf[i][j];
      suf_sum[i][j] = suf_s % int(1e9 + 7);
    }
    insert(1, 1, szz, i);
  }
  long long int ans = 0;
  for (int i = 1; i <= idx + 1; ++i) {
    int szz = (int)dataidx[i].size();
    for (int j = 0; j < szz; ++j) {
      if (j + 3 <= szz) {
        ans += (pre[i][j] * get_suffix_sum(1, 1, szz, (j + 3), i, 0)) %
               int(1e9 + 7);
        ans %= int(1e9 + 7);
      }
    }
  }
  int m, qidx, qtype, szz, nxtOne, nxtTwo, prvOne, prvTwo;
  scanf("%d", &m);
  ;
  while (m--) {
    scanf("%d", &qtype);
    ;
    scanf("%d", &qidx);
    ;
    szz = (int)dataidx[a[qidx]].size();
    int id = a[qidx];
    prvOne = prvTwo = -1;
    nxtOne = nxtTwo = -1;
    if (pos[qidx] > 1) prvOne = get_prv(1, 1, szz, pos[qidx] - 1, id);
    if (prvOne > 1) prvTwo = get_prv(1, 1, szz, prvOne - 1, id);
    if (pos[qidx] < szz) nxtOne = get_nxt(1, 1, szz, pos[qidx] + 1, id);
    if (nxtOne < szz && nxtOne > 0) nxtTwo = get_nxt(1, 1, szz, nxtOne + 1, id);
    if (qtype == 1) {
      if (pos[qidx] > 1 && pos[qidx] < szz)
        ans -= (get_prefix(1, 1, szz, pos[qidx] - 1, id) *
                get_suffix(1, 1, szz, pos[qidx] + 1, id)) %
               int(1e9 + 7);
      if (nxtTwo != -1 && nxtTwo <= szz)
        ans -= (pre[id][pos[qidx] - 1] *
                get_suffix_sum(1, 1, szz, nxtTwo, id, 0)) %
               int(1e9 + 7);
      if (prvTwo > 0)
        ans -= (get_prefix_sum(1, 1, szz, prvTwo, id, 0) *
                suf[id][pos[qidx] - 1]) %
               int(1e9 + 7);
      long long int val = pre[id][pos[qidx] - 1];
      point_update(1, 1, szz, pos[qidx], false, a[qidx]);
      range_update_prefix(1, 1, szz, pos[qidx], id, val, false);
      val = suf[id][pos[qidx] - 1];
      range_update_suffix(1, 1, szz, pos[qidx], id, val, false);
    } else {
      if (pos[qidx] > 1 && pos[qidx] < szz)
        ans += (get_prefix(1, 1, szz, pos[qidx] - 1, id) *
                get_suffix(1, 1, szz, pos[qidx] + 1, id)) %
               int(1e9 + 7);
      if (nxtTwo != -1 && nxtTwo <= szz)
        ans += (pre[id][pos[qidx] - 1] *
                get_suffix_sum(1, 1, szz, nxtTwo, id, 0)) %
               int(1e9 + 7);
      if (prvTwo > 0)
        ans += (get_prefix_sum(1, 1, szz, prvTwo, id, 0) *
                suf[id][pos[qidx] - 1]) %
               int(1e9 + 7);
      long long int val = pre[id][pos[qidx] - 1];
      point_update(1, 1, szz, pos[qidx], true, a[qidx]);
      range_update_prefix(1, 1, szz, pos[qidx], id, val, true);
      val = suf[id][pos[qidx] - 1];
      range_update_suffix(1, 1, szz, pos[qidx], id, val, true);
    }
    ans %= int(1e9 + 7);
    if (ans < 0) ans += int(1e9 + 7);
    printf("%d\n", (int)(ans));
  }
  return 0;
}