#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #include #include #include #include namespace mp__=boost::multiprecision; using bint=mp__::cpp_int; using greatd=mp__::number>; using namespace std; template using V=vector; template using VV=V>; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using pli=pair; using pil=pair; using pdd=pair; using vi=vector; using vvi=V; using vpi=vector; using vvpi=V; using vl=vector; using vvl=V; using vs=vector; using vvs=V; using vc=vector; using vvc=V; using vd=vector; using vvd=V; using vpl=vector; using vvpl=V; using vpil=vector>; using vvpil=V; using vpli=vector>; using vvpli=V; using vpd=vector; using vvpd=V; using vb=vector; using vvb=V; template using pq=priority_queue,greater>; template using rpq=priority_queue>; templateostream &operator<<(ostream &os,const pair &p){os <istream &operator>>(istream &is,pair &p){is >>p.first >>p.second;return is;} #define ovl4(a,b,c,d,name,...) name #define rep1(n) for(int i=0; i=0; --i) #define rrep2(i,a) for(int i=int(a)-1; i>=0; --i) #define rrep3(i,a,b) for(int i=int(a)-1; i>=b; --i) #define rrep4(i,a,b,c) for(int i=int(a)-1; i>=b; i-=c) #define rrep(...) ovl4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define atrep(i,v) for(auto i:v) void in(){} templatevoid in(T&... a){(cin >>... >>a);} template void vin(vector &v,int n=-1,int s=0){if(n==-1)n=v.size();rep(i,s,s+n)in(v[i]);} #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) void VIN(){} template void VIN(int ind,vector& v,Ts&... vs){vin(v,v.size()-ind,ind);if constexpr(sizeof...(vs)>0)VIN(ind,vs...);} template bool chmax(T &a,Ts... b){T c=a;for(auto i:{b...})a=max(a,i);return a==c;} template bool chmin(T &a,Ts... b){T c=a;for(auto i:{b...})a=min(a,i);return a==c;} template bool chcomp(function comp,T &a,Ts... b){T c=a;for(auto i:{b...})a=comp(a,i);return a==c;} void print(){cout<<"\n";} template void print(const T &a,const Ts&... b){cout < void vprint(vector &v,bool ind1=false,string aid=" "){rep(i,(int)ind1,v.size()){if(i>(int)ind1){cout < bool eql(const T &a){return true;}; template bool eql(const T& a,const Ts&... b){bool ret=true;for(auto i:{b...})ret&=(i==a);return ret;} bool operator==(const string& a,const string& b){return a.compare(b)==0;} random_device rd; mt19937 mt(rd()); const int INF=1e9; const ll LINF=1e18; const ll MOD=1e9+7; const ll MMOD=998244353; const ld eps=1e-10; const ld PI=M_PI; bool deql(const ld &a){return true;} template bool deql(const ld& a,const Args&... b){bool ret=true;for(auto i:{b...})ret&=(inr(-eps,i-a,eps));return ret;} int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1}; class xorshift{ private:uint64_t x; public: xorshift(){mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());x=rnd();for(int i=0; i<100; i++)random();} uint64_t random(){x=x^(x<<7);return x=x^(x>>9);} };xorshift rnd; template class segmenttree{ private: std::vector dat; int size,n; public: segmenttree():segmenttree(0){} explicit segmenttree(int n_):segmenttree(std::vector(n_,e())){} explicit segmenttree(int n_,T init):segmenttree(std::vector(n_,init)){} explicit segmenttree(const std::vector& v):n(int(v.size())){ size=1; while(size=1; --i)dat[i]=op(dat[i<<1],dat[i<<1|1]); } void set(int pos,T x){ pos+=size; dat[pos]=x; while(pos>1){ pos>>=1; dat[pos]=op(dat[pos<<1],dat[pos<<1|1]); } } void add(int pos,T x){ pos+=size; dat[pos]+=x; while(pos>1){ pos>>=1; dat[pos]=op(dat[pos<<1],dat[pos<<1|1]); } } T prod(int l,int r)const{ T resl=e(),resr=e(); l+=size; r+=size; while(l>=1; r>>=1; } return op(resl,resr); } T get(int pos)const{return dat[pos+size];} T operator[](int pos)const{return dat[pos+size];} T all_prod()const{return dat[1];} int max_right(int l,auto f)const{ if(l==n)return n; l+=size; T t=e(); do{ while(l&1==0)l>>=1; if(!f(op(t,dat[l]))){ while(l1 && (r&1)==0)r>>=1; if(!f(op(dat[r],t))){ while(r class lazysegtree{ private: int size,n,log; std::vector dat; std::vector lazy; void all_apply(int pos,F f){ dat[pos]=mapping(f,dat[pos]); if(pos(n_,e())){} explicit lazysegtree(int n_,T init):lazysegtree(std::vector(n_,init)){} explicit lazysegtree(const std::vector& v):n(int(v.size())){ size=1; while(size>=1; dat.assign(size<<1,e()); lazy.assign(size<<1,id()); for(int i=0; i=1; --i)update(i); } void set(int pos,T x){ pos+=size; for(int i=log; i>=1; --i)push(pos>>i); dat[pos]=x; for(int i=1; i<=log; ++i)update(pos>>i); } T get(int pos){ pos+=size; for(int i=log; i>=1; --i)push(pos>>i); return dat[pos]; } T prod(int l,int r){ if(l==r)return e(); l+=size; r+=size; for(int i=log; i>=1; --i){ if(((l>>i)<>i); if(((r>>i)<>i); } T resl=e(),resr=e(); while(l>=1; r>>=1; } return op(resl,resr); } T all_prod(){return dat[1];} void apply(int pos,F f){ pos+=size; for(int i=log; i>=1; --i)push(pos>>i); dat[pos]=mapping(f,dat[pos]); for(int i=1; i<=log; ++i)update(pos>>i); } void apply(int l,int r,F f){ if(l==r)return; l+=size; r+=size; for(int i=log; i>=1; --i){ if(((l>>i)<>i); if(((r>>i)<>i); } { int l2=l,r2=r; while(l>=1; r>>=1; } l=l2,r=r2; } for(int i=1; i<=log; ++i){ if(((l>>i)<>i); if(((r>>i)<>i); } } int max_right(int l,auto g){ if(l==n)return n; l+=size; for(int i=log; i>=1; --i)push(l>>i); T t=e(); do{ while((l&1)==0)l>>=1; if(!g(op(t,dat[l]))){ while(l=1; --i)push((r-1)>>i); T t=e(); do{ r--; while(r>1 && (r&1)==0)r>>=1; if(!g(op(dat[r],t))){ while(r::max();} int main(){ ios::sync_with_stdio(false);std::cin.tie(nullptr);cout.tie(nullptr);FIX; INT(n,q); vi a(n); vin(a); segmenttree sg(a); vector index(n+1); rep(i,n)index[a[i]]=i+1; while(q--){ INT(t,l,r); --l; if(t==1){ --r; int lef=sg[l],rig=sg[r]; sg.set(l,rig),sg.set(r,lef); swap(index[lef],index[rig]); } if(t==2)print(index[sg.prod(l,r)]); } return 0; }