River.1208

#include <bits/stdc++.h>

using namespace std;

const int MAX_CNT_NODES = 200001;

struct Node
{
  int value, cnt, y;
  int left, right;

  Node(int val = 0): value(val), cnt(1), left(0), right(0), y(0) { }
  void gen_y()
  {
    y = (rand() << 15) + rand();
  }
};

Node nodes[MAX_CNT_NODES + 1];
vector<bool> used(MAX_CNT_NODES + 1, false);
queue<int> free_nodes;

void init_free_nodes_queue()
{
  for(int i=1; i<=MAX_CNT_NODES; ++i)
    free_nodes.push(i);
}

int alloc_node()
{
  if (!free_nodes.size())
    return 0;
  int i = free_nodes.front();
  free_nodes.pop();
  return i;
}

void free_node(int i)
{
  used[i] = false;
  free_nodes.push(i);
  if (nodes[i].left) free_node(nodes[i].left);
  if (nodes[i].right) free_node(nodes[i].right);
}

struct Cartesian
{
    int root;

    Cartesian(): root(0) { srand(time(0)); }

    int get_cnt(const int & node)
    {
      if ( !node ) return 0;
      return nodes[node].cnt;
    }

    void update_cnt(const int &node)
    {
      if (!node) return;
      int left_cnt = get_cnt(nodes[node].left);
      int right_cnt = get_cnt(nodes[node].right);
      nodes[node].cnt = left_cnt + right_cnt + 1;
    }

    int get_node(const int & node, int i)
    {
      if (!node) return node;
      int left_k = get_cnt(nodes[node].left);
      if (i == left_k) return node;
      if (i < left_k)
        return get_node(nodes[node].left, i);
      else
        return get_node(nodes[node].right, i - left_k - 1);
    }

    Node & operator[](int i)
    {
      if (i >= 0)
        return nodes[get_node(root, i)];
      return nodes[0];
    }

    // [1 .. k] [k+1 ... n]
    pair<int, int> split(const int & node, int k)
    {
      if (!node) return {0, 0};
      int left_k = get_cnt(nodes[node].left);
      if (k <= left_k )
      {
        auto res = split(nodes[node].left, k);
        nodes[node].left = res.second;
        update_cnt(node);
        return {res.first, node};
      }
      else
      {
        auto res = split(nodes[node].right, k - 1 - left_k);
        nodes[node].right = res.first;
        update_cnt(node);
        return {node, res.second};
      }
    }

    int merge(const int & node1, const int & node2)
    {
      if ( !node1 ) return node2;
      if ( !node2 ) return node1;
      if ( nodes[node1].y <= nodes[node2].y )
      {
        nodes[node1].right = merge(nodes[node1].right, node2);
        update_cnt(node1);
        return node1;
      }
      else
      {
        nodes[node2].left = merge(node1, nodes[node2].left);
        update_cnt(node2);
        return node2;
      }
    }

    // after k
    int insert(const int & val, const int & k, bool & error)
    {
      error = false;
      if (k > get_cnt(root) + 1) return root;
      auto res = split(root, k);
      int nnode = alloc_node();
      if (!nnode)
      {
        error = true;
        return root;
      }
      nodes[nnode].gen_y();
      nodes[nnode].value = val;
      nodes[nnode].cnt = 1;
      root = merge(merge(res.first, nnode), res.second);
      return root;
    }

    int erase(const int & k)
    {
      if (k > get_cnt(root)) return root;
      auto res1 = split(root, k);
      auto res2 = split(res1.first, k-1);
      // non-resursion delete
      nodes[res2.second].value = nodes[res2.second].left = nodes[res2.second].right = 0;
      free_node(res2.second);
      root = merge(res2.first, res1.second);
      return root;
    }

    inline int size() { return get_cnt(root); }

    void print()
    {
      for(int i=0; i<size(); ++i)
      {
        cout << nodes[get_node(root, i)].value << " ";
      }
      cout << endl;
    }
};

void solve_cartesian()
{
  init_free_nodes_queue();
  Cartesian manufactures;
  int n;
  cin >> n;
  unsigned long long sum2 = 0;
  for(int i=0; i<n; ++i)
  {
    bool insert_error = false;
    int len;
    cin >> len;
    sum2 += len * len;
    manufactures.insert( len, i + 1, insert_error );
    assert(!insert_error);
  }
  cout << sum2 << '\n';
  int k;
  cin >> k;
  for(int event = 0; event < k; ++event)
  {
    int e, v;
    cin >> e >> v;

    if (e == 1)
    { // erase
      Node & deleted = manufactures[v-1];
      int value = deleted.value;
      sum2 -= 1LL * value * value;
      Node & prev = manufactures[v-2];
      Node & next = manufactures[v];

      if (v > 1 && v < manufactures.size())
      {
        sum2 -= 1LL * next.value * next.value + 1LL * prev.value * prev.value;
        prev.value += value / 2;
        next.value += value / 2 + value % 2;
        sum2 += 1LL * next.value * next.value + 1LL * prev.value * prev.value;
      }
      else if  (v > 1)
      {
        sum2 -= 1LL * prev.value * prev.value;
        prev.value += value;
        sum2 += 1LL * prev.value * prev.value;
      }
      else
      {
        sum2 -= 1LL * next.value * next.value;
        next.value += value;
        sum2 += 1LL * next.value * next.value;
      }

      manufactures.erase(v);
    }
    else
    { //
      Node & updated = manufactures[v-1];
      int value = updated.value;
      sum2 -= 1LL * value * value;
      int nvalue = value / 2 + value % 2;
      bool insert_error = false;
      manufactures.insert(nvalue, v, insert_error);
      value = updated.value = value / 2;
      sum2 += (1LL * value * value + 1LL * nvalue * nvalue);
      assert(!insert_error);
    }
    cout << sum2 <<  '\n';
    // manufactures.print();
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(0));
  // freopen("INPUT.TXT", "r", stdin);
  // freopen("OUTPUT.TXT", "w", stdout);
  solve_cartesian();
}