import java.io.*; import java.util.*; import java.util.function.BiFunction; 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}; public static void solve(){ //TODO:Solve problem like *** Scanner sc=new Scanner(); int n = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); int[] xs = new int[n]; for (int i = 0; i < n; i++) { xs[i] = sc.nextInt(); } UnionFind uf=new UnionFind(n); boolean[] added=new boolean[n];//unionしただけでサイズが変わるので、計算済みか?にはuf.sizeは使えない? for (int i = 0; i < xs.length; i++) { if(uf.size(i)>1)continue; Deque deq = new ArrayDeque<>(); deq.add(i); while(!deq.isEmpty()){ int node = deq.removeFirst(); if(added[node])continue; uf.union(i,node); added[node]=true; int ok=n; int ng=-1; while (abs(ok - ng) > 1) { int mid=(ok+ng)/2; if(xs[mid]>=xs[node]+a){ ok=mid; }else{ ng=mid; } } for(int j=ok;j 1) { int mid=(ok+ng)/2; if(xs[mid]>=xs[node]-b){ ok=mid; }else{ ng=mid; } } for(int j=ok;j (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< 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