BALLDROP

#define task "E"

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstring>
#include <functional>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
constexpr int Inf = 1e9 + 7;

struct FenwickTree
{
    int n;
    ll a[N];

    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }

    void Update(int p, ll v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }

    ll Get(int p)
    {
        ll ans(0);
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }

    ll Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} g;

struct Edge
{
    int x, y, id;
    Edge(int x = 0, int y = 0, int id = 0) : x(x), y(y), id(id) {}
};

vector<Edge> st[N], res;

struct Queries
{
    int t, x, y;
} s[N];

int n, m, q, p[N], id[N], in[N], pos[N];

void Read()
{
    cin >> n >> m;
    g.n = n;

    for (int i = 1; i <= m; ++i)
    {
        cin >> p[i];
        st[i].emplace_back(p[i], p[i] + 1, Inf);
    }

    cin >> q;

    for (int i = 1; i <= q; ++i)
        cin >> s[i].t >> s[i].x >> s[i].y;
}

void Swap(int x, int y)
{
    swap(id[x], id[y]);
    in[id[x]] = x;
    in[id[y]] = y;
}

void DAC(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    DAC(l, mid);
    DAC(mid + 1, r);

    for (int i = mid; i >= l; --i)
        Swap(res[i].x, res[i].y);

    vector<Edge> tmp;

    for (int i = l, j = mid + 1; i <= mid || j <= r;)
    {
        if (j > r)
        {
            tmp.emplace_back(res[i]);
            Swap(res[i].x, res[i].y);
            ++i;
        }
        else if (i > mid)
        {
            tmp.emplace_back(in[res[j].x], in[res[j].y], res[j].id);
            ++j;
        }
        else if (res[i].id >= res[j].id)
        {
            tmp.emplace_back(res[i]);
            Swap(res[i].x, res[i].y);
            ++i;
        }
        else
        {
            tmp.emplace_back(in[res[j].x], in[res[j].y], res[j].id);
            ++j;
        }
    }

    for (int i = r - l; ~i; --i)
        res[l + i] = tmp[i];
}

void Solve()
{
    for (int i = 1; i <= q; ++i)
        if (s[i].t == 1)
        {
            st[s[i].x].back().id = i;
            p[s[i].x] = s[i].y;

            st[s[i].x].emplace_back(s[i].y, s[i].y + 1, i);
            st[s[i].x].emplace_back(s[i].y, s[i].y + 1, Inf);
        }

    for (int i = 1; i <= n; ++i)
        id[i] = in[i] = pos[i] = i;

    vector<Edge> tmp;

    for (int i = m; i; --i)
        for (auto j : st[i])
            tmp.emplace_back(j);


    for (auto i = tmp.rbegin(); i != tmp.rend(); ++i)
    {
        if (i->id < Inf)
            res.emplace_back(id[i->x], id[i->y], i->id);
        Swap(i->x, i->y);
    }

    for (int i = 1; i <= n; ++i)
        id[i] = in[i] = pos[i] = i;

    DAC(0, res.size() - 1);

    reverse(res.begin(), res.end());

    for (auto i = tmp.rbegin(); i != tmp.rend(); ++i)
        if (i->id == Inf)
            res.emplace_back(*i);

    reverse(res.begin(), res.end());

    for (auto i : res)
        Swap(i.x, i.y);

    for (int i = 1; i <= n; ++i)
        g.Update(id[i], 1ll * i * i);

    for (int i = 1; i <= q; ++i)
    {
        while (!res.empty() && res.back().id == i)
        {
            g.Update(id[res.back().x], -1ll * res.back().x * res.back().x);
            g.Update(id[res.back().y], -1ll * res.back().y * res.back().y);

            swap(id[res.back().x], id[res.back().y]);

            g.Update(id[res.back().x], 1ll * res.back().x * res.back().x);
            g.Update(id[res.back().y], 1ll * res.back().y * res.back().y);

            res.pop_back();
        }

        if (s[i].t == 2)
            cout << g.Get(s[i].x, s[i].y) << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    {
        Read();
        Solve();
    }
}