import java.util.*; import java.io.*; class Main{ public static void solve(Read br,Write out){ //out.debug=true; int n=br.readI(),k=br.readI(); int a[] = br.readIs(n); int l=0,r=n+1; int len=0; int ans = -1; for(int i=0;ia[i+1]){ l+=len+1; len=0; if(l>=k){ ans=i; break; } }else if(a[i]> child; int lca[][]; public Tree(int nn,int r){ n=nn;root=r; parent = new int[n]; height = new int[n]; child = new ArrayList<>(); for(int i=0;i()); } } public Tree(int par[],int r){ n=par.length;root=r; parent = new int[n]; height = new int[n]; child = new ArrayList<>(); for(int i=0;i()); } for(int i=0;i q=new ArrayDeque<>(); q.add(root); while(q.size()>0){ int v=q.poll(); for(int u:child.get(v)){ height[u]=height[v]+1; if(height[u]>maxh){ maxh=height[u]; } q.add(u); } } } public Tree(Graph g,int r){ this(g.n,r); construct(g); } public void construct(Graph g){ constructdfs(g,root,-1,0,new boolean[n]); } public void constructdfs(Graph g,int now,int before,int h,boolean flg[]){ flg[now]=true; parent[now]=before; height[now]=h; if(h>maxh){ maxh=h; } for(Graph.Edge e:g.g.get(now)){ if(e.v!=before){ constructdfs(g,e.v,now,h+1,flg); child.get(now).add(e.v); } } } public void const_lowest_common_ancestor(){ int k = 1; while((1<>i)%2>0){ u=lca[i][u]; } } return u; } public int query_lowest_common_ancestor(int u,int v){ if(height[u]=0;i--){ if(lca[i][u]!=lca[i][v]){ u=lca[i][u]; v=lca[i][v]; } } return lca[0][u]; } } public static int comp(long a,long b){ return a>b ? 1 : a n){ Collections.sort(n); } public static void sortD(ArrayList n){ Collections.sort(n,Collections.reverseOrder()); } public static void sortA(int n[][],int k){ Arrays.sort(n,(a, b) -> Integer.compare(a[k], b[k])); } public static void sortD(int n[][],int k){ Arrays.sort(n,(a, b) -> Integer.compare(b[k], a[k])); } public static void mysort(int n[][],int k){ Arrays.sort(n, new Comparator(){ public int compare(int[] x,int[] y){ if(x[k]==y[k]){ return x[1]-y[1]; } return x[k]-y[k]; } }); } static class ModFunc{ int n; long mod; long fact[],invfact[]; public ModFunc(int n,long mod){ this.n=n;this.mod=mod; fact=new long[n+1];invfact=new long[n+1]; modfact();modinvfact(); } public static long modfact(int n,long mod){ long k=1; for(int i=1;i<=n;i++){ k = k*i % mod; } return k; } public static long modinvfact(int n,long mod){ return modinv(modfact(n,mod),mod); } public static long modinv(long a,long mod){ long x1=1,x2=0; long p=mod,q,t; while(a%p!=0){ q = a/p; t = x1-q*x2; x1=x2; x2=t; t=a%p; a=p; p=t; } return x2<0 ? x2+mod : x2; } private void modfact(){ fact[0]=1; for(int i=1;i<=n;i++){ fact[i] = fact[i-1]*i % mod; } } private void modinvfact(){ invfact[n]=modinv(fact[n],mod); for(int i=n-1;i>=0;i--){ invfact[i] = invfact[i+1]*(i+1) % mod; } } public long modConv(int n,int k){ return ((fact[n]*invfact[n-k])%mod)*invfact[k]%mod; } public static long modpow(long x,long n,long pow){ long r = 1; while(n>=1){ if(1==(n&1)){ r = r*x % pow; } x = x*x % pow; n/=2; } return r; } } static class Permu{ int n; public int a[]; boolean flg; public Permu(int n){ this.n=n;flg=true; a=new int[n]; for(int i=0;i=0;i--){ if (a[i]=0;i--){ if (a[i]>a[i+1]){ for (int j=n-1;;j--){ if (a[i] > a[j]){ int temp=a[i]; a[i]=a[j]; a[j] = temp; i++; for (j=n-1;i a; HashMap map; public Compress(int[]b){ HashSet temp = new HashSet<>(); for(int i:b){ temp.add(i); } a=new ArrayList(temp); setup(); } public Compress(ArrayListb){ a=new ArrayList(new HashSet(b)); setup(); } private void setup(){ map = new HashMap<>(); sortA(a); for(int i=0;i0){ now = (now-1)/2; ar[now] = func(ar[now*2+1],ar[now*2+2]); } } public void add(int i,int x){ update(i,ar[i+leafN-1]+x); } public int get(int i){ return ar[i+leafN-1]; } public int query(int a,int b){ return query(a,b,0,0,leafN); } public int query(int a,int b,int k,int l,int r){ if(r<=a||b<=l){ return temp; }else if(a<=l&&r<=b){ return ar[k]; } int t1=query(a,b,k*2+1,l,(l+r)/2),t2=query(a,b,k*2+2,(l+r)/2,r); return func(t1,t2); } private int twon(int x){ int i=1; while(i0;ii-=(ii&-ii)){ k+=ar[ii]; } return k; } private int twon(int x){ int i=1; while(i> g; public Graph(int nn){ n=nn; g=new ArrayList>(); for(int i=0;i()); } } public void add(int a,int b,int d){ g.get(a).add(new Edge(b,d)); g.get(b).add(new Edge(a,d)); } public void addY(int a,int b,int d){ g.get(a).add(new Edge(b,d)); } public void add(int a,int b){ g.get(a).add(new Edge(b,1)); g.get(b).add(new Edge(a,1)); } public void addY(int a,int b){ g.get(a).add(new Edge(b,1)); } public int len(int a){ return g.get(a).size(); } public long[][] dijkstra(int s){ long dist[][]=new long[n][2]; for(int i=0;i q = new PriorityQueue(new Comparator(){ public int compare(long[] x,long[] y){ return Long.compare(x[1],y[1]); } }); q.add(new long[]{s,0L}); while(q.size()>0){ long[] p = q.poll(); if(dist[(int)p[0]][0]!=p[1]){continue;} for(Edge e:g.get((int)p[0])){ if(dist[e.v][0]>dist[(int)p[0]][0]+e.d){ dist[e.v][0]=dist[(int)p[0]][0]+e.d; dist[e.v][1] = (int)p[0]; q.add(new long[]{e.v,dist[e.v][0]}); } } } return dist; } public void dfs(int v){ ArrayDeque q = new ArrayDeque<>(); boolean flg[]=new boolean[n]; q.addLast(v); flg[v]=true; while(q.size()>0){ int now=q.pollLast(); for(Edge e:g.get(now)){ if(!flg[e.v]){ flg[e.v]=true; q.addLast(e.v); } } } } public void bfs(int s){ boolean flg[]=new boolean[n]; Queue q = new ArrayDeque(); q.add(s); while(q.size()>0){ int v = q.poll(); flg[v]=true; for(Edge e:g.get(v)){ if(!flg[e.v]){ q.add(e.v); flg[e.v]=true; }}} } public int minspantree(){ PriorityQueue q = new PriorityQueue(new Comparator(){ public int compare(Edge a, Edge b) { return a.d-b.d; } }); boolean flg[]=new boolean[n]; int c=1,sum=0; for(Edge e:g.get(0)){ q.add(e); } flg[0]=true; while(c list = new ArrayList(); boolean flg[]=new boolean[n]; boolean end[]=new boolean[n]; ArrayDeque q = new ArrayDeque<>(); for(int i=0;i0){ int v=q.pollLast(); if(v<0){ v=-v-1; if(end[v]){continue;} end[v]=true; list.add(v); continue; } v--; if(flg[v]){continue;} flg[v]=true; for(Edge e:g.get(v)){ if(flg[e.v]){continue;} q.addLast(-e.v-1); q.addLast(e.v+1); } } } return g2.scc1_2(list); } public int[] scc1_2(ArrayListlist){ boolean flg[]=new boolean[n]; int ren[]=new int[n]; ArrayDeque q = new ArrayDeque<>(); int num=0; for(int i=n-1;i>=0;i--){ int now = list.get(i); if(flg[now]){continue;} q.add(now); flg[now]=true; while(q.size()>0){ int v=q.poll(); ren[v]=num; for(Edge e:g.get(v)){ if(flg[e.v]){continue;} flg[e.v]=true; q.add(e.v); } } num++; } return ren; } public int[] scc(){ Graph g2 = new Graph(n); for(int i=0;i list = new ArrayList(); boolean flg[]=new boolean[n]; for(int i=0;ilist){ boolean flg[]=new boolean[n]; int ren[]=new int[n]; int num=0; for(int i=n-1;i>=0;i--){ int now = list.get(i); if(!flg[now]){ dfs_scc2(now,flg,ren,num); num++; } } return ren; } private void dfs_scc(int v,boolean flg[],ArrayListlist){ flg[v]=true; for(Edge e:g.get(v)){ if(!flg[e.v]){ dfs_scc(e.v,flg,list); } } list.add(v); } private void dfs_scc2(int v,boolean flg[],int num[],int now){ flg[v]=true; num[v]=now; for(Edge e:g.get(v)){ if(!flg[e.v]){ dfs_scc2(e.v,flg,num,now); } } } public ArrayList> two_Edge_connected(){ int ord[]=new int[n],low[]=new int[n]; boolean flg[]=new boolean[n]; for(int i=0;i> list = new ArrayList<>(); int now=0; for(int i=0;i()); tecDfs2(i,flg,ord,low,list.get(now)); now++; } } return list; } public void tecDfs(int v,boolean flg[],int ord[],int low[],int before){ flg[v]=true; if(before!=-1){ ord[v] = ord[before]+1; }else{ ord[v] = 0; } low[v]=ord[v]; for(Edge e:g.get(v)){ if(e.v==before){before=-1;continue;} if(flg[e.v]){ low[v] = Math.min(low[v],ord[e.v]); }else{ tecDfs(e.v,flg,ord,low,v); low[v] = Math.min(low[v],low[e.v]); } } } public void tecDfs2(int v,boolean flg[],int ord[],int low[],ArrayList list){ flg[v]=true; list.add(v); for(Edge e:g.get(v)){ if(flg[e.v]){continue;} if(ord[v]{ T a; U b; public Pair(T t,U u){ a=t;b=u; } public T first(){ return a; } public T second(){ return a; } } static class Read{ BufferedReader br; public Read(){ br = new BufferedReader(new InputStreamReader(System.in)); } private boolean canprint(int a){ return 33<=a&&a<=126; } private int skipread(){ int a=readC(); while(a!=-1&&!canprint(a)){ a=readC(); } return a; } public char readC(){ try{ return (char)br.read(); }catch(IOException e){ e.printStackTrace(); return (char)-1; } } public String readLine(){ try{ return br.readLine(); }catch(IOException e){ e.printStackTrace(); return ""; } } public String readS(){ StringBuilder sb = new StringBuilder(); int k = skipread(); while(true){ if(!canprint(k)){break;} sb.append((char)k); k = readC(); } return sb.toString(); } public int readI(){ int r = 0; int k = skipread(); int flg = 1; if(k=='-'){ flg=-1; k=readC(); } while(true){ if(!canprint(k)){break;} r = r*10+(k-'0'); k = readC(); } return flg*r; } public long readL(){ long r = 0; int k = skipread(); int flg = 1; if(k=='-'){ flg=-1; k=readC(); } while(true){ if(!canprint(k)){break;} r = r*10+(k-'0'); k = readC(); } return flg*r; } public String[] readSs(int n){ String[]a = new String[n]; for(int i=0;ivoid pr(T str){ out.print(str); } public void pl(T str){ out.println(str); } public void pr(int[]a){ int t=a.length; if(t>0){pr(a[0]);} for(int i=1;i0){pr(a[0]);} for(int i=1;i0){pr(a[0]);} for(int i=1;ivoid prA(T str){ System.out.print(str); } public static void plA(T str){ System.out.println(str); } public static void prA(int[]a){ int t=a.length; if(t>0){prA(a[0]);} for(int i=1;i0){prA(a[0]);} for(int i=1;i0){prA(a[0]);} for(int i=1;ivoid debugP(T str){ if(debug){ pl(str); } } } public static long stol(String s){ return Long.parseLong(s); } public static int stoi(String s){ return Integer.parseInt(s); } public static int[] stoi(String s[]){ int a[]=new int[s.length]; for(int i=0;i