#include <iostream>
#include <chrono>
#include <random>
#include <map>
#include <algorithm>
using namespace std;
using ll=long long;
const int MN=1e6+13;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rng(0);
ll mp[MN];
int N, Q;
int A[MN], B[MN];
int dsu[MN]; ll sz[MN];
ll res[MN], cor[MN];
map<ll, ll> cnt;
ll ans;
ll get(ll x) { return x*(x-1)/2; }
ll contribution(ll x) { return cnt[x]*cnt[-x]; }
int find(int x)
{
if (dsu[x]==x) return x;
else return dsu[x]=find(dsu[x]);
}
bool unite(int x, int y)
{
x=find(x); y=find(y);
if (x==y) return 0;
//cerr<<"UNITE "<<x<<' '<<y<<endl;
//cerr<<(res[x]^cor[x])<<' '<<(res[y]^cor[y])<<": "<<ans<<endl;
if (res[x]-cor[x]) ans-=contribution(res[x]-cor[x]);
cnt[res[x]-cor[x]]-=sz[x];
if (res[x]-cor[x]) ans+=contribution(res[x]-cor[x]);
if (res[y]-cor[y]) ans-=contribution(res[y]-cor[y]);
cnt[res[y]-cor[y]]-=sz[y];
if (res[y]-cor[y]) ans+=contribution(res[y]-cor[y]);
dsu[y]=x; sz[x]+=sz[y];
res[x]+=res[y]; cor[x]+=cor[y];
if (res[x]-cor[x]) ans-=contribution(res[x]-cor[x]);
cnt[res[x]-cor[x]]+=sz[x];
if (res[x]-cor[x]) ans+=contribution(res[x]-cor[x]);
//cerr<<(res[x]^cor[x])<<": "<<ans<<endl;
return 1;
}
int main()
{
for (int i=0; i<MN; i++) mp[i]=rng();
cin>>N>>Q;
for (int i=1; i<=N; i++)
{
cin>>A[i];
B[i]=A[i];
}
sort(B+1, B+1+N);
for (int i=1; i<=N; i++)
{
dsu[i]=i; sz[i]=1;
res[i]=mp[A[i]];
cor[i]=mp[B[i]];
cnt[res[i]-cor[i]]++;
}
for (auto [x, y]:cnt)
{
//cerr<<x<<": "<<y<<endl;
if (x) ans+=contribution(x);
}
ans/=2;
//cerr<<ans<<endl;
while (Q--)
{
int T; cin>>T;
if (T==1)
{
int x, y; cin>>x>>y;
int rx=find(x), ry=find(y);
if (res[rx]-cor[rx]) ans-=contribution(res[rx]-cor[rx]);
cnt[res[rx]-cor[rx]]-=sz[rx];
if (res[rx]-cor[rx]) ans+=contribution(res[rx]-cor[rx]);
if (res[ry]-cor[ry]) ans-=contribution(res[ry]-cor[ry]);
cnt[res[ry]-cor[ry]]-=sz[ry];
if (res[ry]-cor[ry]) ans+=contribution(res[ry]-cor[ry]);
res[rx]-=mp[A[x]];
res[ry]-=mp[A[y]];
swap(A[x], A[y]);
res[rx]+=mp[A[x]];
res[ry]+=mp[A[y]];
if (res[rx]-cor[rx]) ans-=contribution(res[rx]-cor[rx]);
cnt[res[rx]-cor[rx]]+=sz[rx];
if (res[rx]-cor[rx]) ans+=contribution(res[rx]-cor[rx]);
if (res[ry]-cor[ry]) ans-=contribution(res[ry]-cor[ry]);
cnt[res[ry]-cor[ry]]+=sz[ry];
if (res[ry]-cor[ry]) ans+=contribution(res[ry]-cor[ry]);
}
else if (T==2)
{
int x, y; cin>>x>>y;
unite(x, y);
}
else if (T==3)
{
if (cnt[0]==N) cout<<"DA"<<endl;
else cout<<"NE"<<endl;
}
else cout<<ans<<endl;
//for (auto [x, y]:cnt) cerr<<x<<": "<<y<<endl; cerr<<ans<<endl;
}
return 0;
}
