import java.io.*; import java.math.BigInteger; import java.util.*; import java.util.stream.Collectors; import java.util.stream.IntStream; import static java.lang.Math.*; import static java.lang.String.format; public class Main { public static void main(String[] args) { solve(); } final static int INF = Integer.MAX_VALUE>>1; final static int MOD = 1_000_000_007; final static int[] dx4 = { 0, 1, 0, -1 }; final static int[] dy4 = { 1, 0, -1, 0 }; final static int[] dx8 = {0, 1, 1, 1, 0, -1, -1, -1}; final static int[] dy8 = {1, 1, 0, -1, -1, -1, 0, 1}; final static Runnable me=()->{}; public static void solve(){ //TODO:Solve problem like *** Scanner sc=new Scanner(); int n = sc.nextInt(); int q = sc.nextInt(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } SegmentTree.MinSegmentTree mst=new SegmentTree.MinSegmentTree(a); Map map = new HashMap<>(); for (int i = 0; i < n; i++) { map.put(a[i],i); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { int x = sc.nextInt(); int l = sc.nextInt()-1; int r = sc.nextInt()-1; if(x==1){ long elementL=mst.getVal(l); long elementR=mst.getVal(r); int rdx=map.get(elementR); int ldx=map.get(elementL); mst.setVal(l,elementR); mst.setVal(r,elementR); map.put(elementL,rdx); map.put(elementR,ldx); }else{ long min=mst.getVal(l,r)+1; sb.append(min + "\n"); } } put(sb); } private static abstract class SegmentTree { private final int originSize; private final int height; private final long[] node; private final long noRelationVal; protected SegmentTree (long[] original,long noRelationVal){ this.noRelationVal=noRelationVal; originSize = original.length; { int height_ = 1; while (originSize > (1 << (height_ - 1))) { height_++; } height = height_; } this.node = new long[ (1<=0; i--){ this.node[i]=marge(this.node[i*2+1],this.node[i*2+2]); } } public long getVal(int a,int b){ return getVal(a,b,0,0,-1); } public long getVal(int a, int b, int k, int l, int r) { //node[k]=origin上の範囲[l,r]の合計を表している if(r < 0) r = (1<<(height-1))-1; if(b=originSize) throw new IllegalArgumentException(format("挿入位置が不正%d",index)); index=(1<<(height-1))-1+index; node[index]=val; while(index>0){ index=(index-1)/2; node[index]=marge(node[2*index+1],node[2*index+2]); } } protected abstract long marge(long a,long b); @Override public String toString(){ StringBuilder result=new StringBuilder(); result.append(format("Class:%s\n",getClass().getSimpleName())); result.append(format("height:%d\n",height)); for(int currentHeight=1;currentHeight<=height;currentHeight++){ for(int i=(1<<(currentHeight-1))-1;i<=(1<{put(objects);}; } } private static void print(Object... objects){ if(objects.length==1){ System.out.print(objects[0]); }else{ System.out.print(Arrays.toString(objects)); } } private static void put(Object... objects) { print(objects); put(); } private static void put(){ System.out.println(); } private static void runWhenEA(Runnable runnable){ try{ assert false; }catch(AssertionError e){ PrintStream ps=System.out; PrintStream pse=System.err; System.setOut(pse); runnable.run(); System.setOut(ps); } } private static void putM(String name,char[][] mat){ put("---------------------"+name+"-----------------"); for (int i = 0; i < mat.length; i++) { put(Arrays.toString(mat[i])); } } private static void putM(String name,int[][] mat){ put("---------------------"+name+"-----------------"); for (int i = 0; i < mat.length; i++) { put(Arrays.toString(mat[i])); } } private static void putM(String name,long[][] mat){ put("---------------------"+name+"-----------------"); for (int i = 0; i < mat.length; i++) { put(Arrays.toString(mat[i])); } } private static void putM(String name,boolean[][] mat){ put("---------------------"+name+"-----------------"); for (int i = 0; i < mat.length; i++) { put(Arrays.toString(mat[i])); } } final static private class Scanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next()); } } final static private class FixedIntPair { final public int x, y; final static public FixedIntPair ZEROS=new FixedIntPair(0,0); FixedIntPair(int x, int y) { this.x = x; this.y = y; } public static double distance(FixedIntPair fip1,FixedIntPair fip2){ double x = (double) fip1.x - fip2.x; double y = (double) fip1.y - fip2.y; return Math.sqrt(x*x+y*y); } @Override public int hashCode() { return x*100000+y; } @Override public boolean equals(Object obj) { if(obj==null)return false; if(!(obj instanceof FixedIntPair)) return false; FixedIntPair pair=(FixedIntPair) obj; return this.x==pair.x&&this.y==pair.y; } @Override public String toString() { return format(FixedIntPair.class.getSimpleName()+":(%d,%d)", x, y); } } final static private class FixedLongPair { final public long x, y; final static public FixedLongPair ZEROS=new FixedLongPair(0,0); FixedLongPair(long x, long y) { this.x = x; this.y = y; } public static double distance(FixedLongPair flp1,FixedLongPair flp2){ double x = (double) flp1.x - flp2.x; double y = (double) flp1.y - flp2.y; return Math.sqrt(x*x+y*y); } @Override public int hashCode() { return (int)x+(int)y; } @Override public boolean equals(Object obj) { if(obj==null)return false; if(!(obj instanceof FixedLongPair)) return false; FixedLongPair pair=(FixedLongPair)obj; return this.x==pair.x&&this.y==pair.y; } @Override public String toString() { return format(FixedLongPair.class.getSimpleName()+":(%d,%d)", x, y); } } final static private class Binary{ public static String toZeroPadding(int i){ return format("%"+Integer.toBinaryString(-1).length()+"s",Integer.toBinaryString(i)).replace(' ','0'); } public static String toZeroPadding(long i){ return format("%"+Long.toBinaryString(-1).length()+"s",Long.toBinaryString(i)).replace(' ','0'); } } final static private class Util { static long gcd(long a,long b){ a= abs(a); b= abs(b); if(a=0&&i=0&&j