#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector
const int MAX_N = 1e6;
ll hsh[MAX_N], h[MAX_N];
int sz[MAX_N], par[MAX_N];
int p[MAX_N], q[MAX_N];
unordered_map<ll,int> paired;
ll pairs = 0, notgood = 0;
int get(int x) {return (par[x]==x ? x : par[x]=get(par[x]));}
void upd_pair(int a, int m) {
if (hsh[a]) {
pairs += (ll)m*sz[a]*paired[-hsh[a]];
paired[hsh[a]] += m*sz[a];
notgood += m;
}
}
void unite(int x, int y) {
int a = get(x), b = get(y);
if (a==b) {return;}
upd_pair(a,-1); upd_pair(b,-1);
if (sz[a]<sz[b]) {swap(a,b);}
par[b] = a; sz[a] += sz[b]; hsh[a] += hsh[b];
// merge sets
upd_pair(a,1);
}
void swp(int x, int y) {
int a = get(x), b = get(y);
if (a!=b) {
upd_pair(a,-1); upd_pair(b,-1);
hsh[a] += h[p[y]]-h[p[x]];
hsh[b] += h[p[x]]-h[p[y]];
upd_pair(a,1); upd_pair(b,1);
}
swap(p[x],p[y]);
}
void pre() {
mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
F0R(i,MAX_N) {h[i] = uniform_int_distribution<ll>(0,INT32_MAX)(gen);}
F0R(i,MAX_N) {
par[i] = i;
sz[i] = 1;
}
// c1+c2=p1+p2; c1-p1 = -(c2-p2)
// let hash be c-p
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
pre();
int n, nq; cin >> n >> nq;
F0R(i,n) {
cin >> p[i];
q[i] = p[i];
}
sort(q,q+n);
F0R(i,n) {
hsh[i] = h[p[i]]-h[q[i]];
}
F0R(i,n) {upd_pair(i,1);}
//cout<<pairs<<'\n';
int j=0;
F0R(i,nq) {
int t; cin >> t;
if (t==1) {
int a, b; cin >> a >> b;
swp(--a,--b);
} else if (t==2) {
int a, b; cin >> a >> b;
unite(--a,--b);
} else if (t==3) {
j++;
cout << (notgood ? "NE" : "DA") << '\n';
} else {
j++;
cout << pairs << '\n';
}
//if (j==154) {cout<<i<<'\n';}
}
}
