#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <time.h>
#include <set>
#include <cmath>
using namespace std;

#pragma comment (linker, "/STACK:136667216")
struct node
{
    node* Left, *Right;
    int val;
    long long sum;
    long long l, r;
    node(long long x, long long y)
    {
        Left = NULL;
        Right = NULL;
        val = 0;
        sum = 0;
        l = x;
        r = y;
    }
};

long long A, B;
long long X;
long long totalsum = 0;

void inc(node *i)
{
    if (i->r < A || i->l > B) return;
    if (i->r <= B && i->l >= A)
    {
        if (X == -1) totalsum -= i->sum * i->sum, i->val = 0, i->sum = 0;
        else totalsum -= i->sum * i->sum, i->val = 1, i->sum = X, totalsum += X * X;
        return;
    }
    if (i->Left == NULL)
        i->Left = new node(i->l, (i->l + i->r) / 2);
    inc(i->Left);
    if (i->Right == NULL)
        i->Right = new node((i->l + i->r) / 2 + 1, i->r);
    inc(i->Right);
    i->val = i->Left->val + i->Right->val;
}

int get(node* i)
{
    //cerr << i->l << " " << i->r << " " << i->val << endl;
    if (i->r < A || i->l > B) return 0;
    if (i->r <= B && i->l >= A) { return i->val; }
    if (i->Right == NULL)
        return get(i->Left);
    if (i->Left == NULL)
        return get(i->Right);
    return get(i->Left) + get(i->Right);
}

long long k2 = (1LL << 30) - 1LL;
node* root = new node(0, k2);

long long gather(int k)
{
    node* cur = root;
    //We guarantee that k is not less than cur->size
    while (cur->l != cur->r)
    {
        if (cur->Left == NULL)
        {
            cur = cur->Right;
            continue;
        }
        if (cur->Right == NULL)
        {
            cur = cur->Left;
            continue;
        }
        if (cur->Left->val < k)
            k -= cur->Left->val, cur = cur->Right;
        else cur = cur->Left;
    }
    return cur->l;
}

long long getsum(node* i)
{
    if ((i->r < A) || (i->l > B)) return 0;
    if ((i->r <= B) && (i->l >= A))
    {
        return i->sum;
    }
    if (i->Right == NULL)
        return getsum(i->Left);
    if (i->Left == NULL)
        return getsum(i->Right);
    return getsum(i->Left) + getsum(i->Right);
}
int main()
{
    freopen("river.in", "r", stdin);
    freopen("river.out", "w", stdout);
    int n, p;
    scanf("%d%d", &n, &p);
    A = 0, B = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> X;
        inc(root);
        A += X;
        B += X;
    }
    int k;
    scanf("%d", &k);
    printf("%I64d\n", totalsum);
    int number = n;
    while (k--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        long long pos = gather(y);
        if (x == 1)
        {
            long long posl, posr;
            if (y > 1)
                posl = gather(y - 1);
            else
                posl = 0;
            if (y < number)
                posr = gather(y + 1);
            else
                posr = k2 - 1;
            if (y == 1)
            {
                A = posr, B = posr;
                X = -1;
                long long g = getsum(root);
                inc(root);
                A = pos, B = pos;
                X = getsum(root) + g;
                inc(root);
                printf("%I64d\n", totalsum);
                number--;
                continue;
            }
            if (posr == k2 - 1)
            {
                A = pos, B = pos;
                X = -1;
                long long g = getsum(root);
                inc(root);
                A = posl, B = posl;
                X = getsum(root) + g;
                inc(root);
                printf("%I64d\n", totalsum);
                number--;
                continue;
            }
            //Оставшийся случай, когда рушится предприятие в центре
            {
                A = posr, B = posr;
                X = -1;
                long long gr = getsum(root);
                inc(root);
                A = pos, B = pos;
                long long gm = getsum(root);
                inc(root);
                A = posl, B = posl;
                long long gl = getsum(root);
                inc(root);
                X = gl + (gm / 2);
                inc(root);
                pos += gm / 2;
                X = gm - (gm / 2) + gr;
                A = pos, B = pos;
                inc(root);
                printf("%I64d\n", totalsum);
                number--;
                continue;
            }
        }
        else
        {
            A = pos, B = pos;
            long long gm = getsum(root);
            X = gm / 2;
            inc(root);
            A += X;
            B += X;
            X = gm - X;
            inc(root);
            printf("%I64d\n", totalsum);
            number++;
            continue;
        }
    }
    return 0;
}