import java.io.*; import java.util.*; class Main { static int q; static int[]t; static long[]x; Main(){ long b=0; long[]c=new long[q]; int p=0; for(int i=0;ihm=new HashMap(); for(int i=0;i0&&c[i]==c[i-1]); else hm.put(c[i],p2++); long[]cc=new long[p2]; p2=0; for(int i=0;i0&&c[i]==c[i-1]); else cc[p2++]=c[i]; PlusSegmentTree st=new PlusSegmentTree(); b=0; for(int i=0;i1){ int y=(ps+fl)/2; if(st.query(y,p2)>=(y>0?cc[y-1]+1+b:-1L<<50)) ps=y; else fl=y; } if(false){ out.println("b="+b); out.print("st:"); for(int j=0;j 0) { x = (x - 1) / 2; this.seg[x] = this.seg[2 * x + 1] + this.seg[2 * x + 2]; } } long query(int l, int r) { l += SIZE - 1; r += SIZE - 1; long y = 0; while (l < r) { if ((l & 1) == 0) { y += this.seg[l]; } if ((r & 1) == 0) { y += this.seg[r - 1]; } l /= 2; r = (r - 1) / 2; } return y; } }