Loj 1084 - Winter

import java.io.*;
import java.lang.reflect.Array;
import java.nio.charset.StandardCharsets;
import java.nio.file.StandardOpenOption;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


public class Main {
    static private int MaxN = 100001;
    static private int Inf = 10000000;
    static class Tree
    {
        private int dp[] = new int[MaxN<<2];
        public void init(int n)
        {
            Arrays.fill(dp,0,n<<2,Inf);
        }

        public int getMin(int cn,int st,int ed,int l,int r)
        {
            if(st==l && ed==r)
            {
                return dp[cn];
            }
            int mid = (st+ed)>>1;
            int lChild = cn<<1;
            int rChild  = 1 | lChild;
            if(r<=mid)return getMin(lChild,st,mid,l,r);
            if(l>mid)return getMin(rChild,mid+1,ed,l,r);
            int lmin = getMin(lChild,st,mid,l,mid);
            int rmin = getMin(rChild,mid+1,ed,mid+1,r);
            return Math.min(lmin,rmin);
        }

        public void setMin(int cn,int st,int ed,int pos,int val)
        {
            if(st==ed)
            {
                dp[cn]=val;
                return ;
            }
            int mid =(st+ed)>>1;
            int lChild = cn<<1;
            int rChild  = 1 | lChild;
            if(pos<=mid)setMin(lChild,st,mid,pos,val);
            else setMin(rChild,mid+1,ed,pos,val);
            dp[cn]=Math.min(dp[lChild],dp[rChild]);
        }
    }

    public static void main(String[] args) throws IOException {

       Reader reader = new Reader().InitConsoleReading();
        //Reader reader = new Reader().InitFileReading("C:\\Users\\najim\\OneDrive\\Documents\\in_large.txt");
        Writer writer = new Writer().InitConsoleWriting();
        //Writer writer = new Writer().InitFileWriting("C:\\Users\\najim\\OneDrive\\Documents\\out_java.txt");
        int totalNumberOfTestCases = reader.nextInt();
        int n,k;
        int[] arr = new int[MaxN];
        Tree tree = new Tree();
        for(int cs=1;cs<=totalNumberOfTestCases;cs++)
        {
            //long beforeUsedMem=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
            n = reader.nextInt();
            k = reader.nextInt();
            k<<=1;

            for(int i=1;i<=n;i++)
            {
                arr[i] = reader.nextInt();
            }
            Arrays.sort(arr,1,n+1);
            tree.init(n);

            for(int i=1;i<=n;i++)
            {
                int l = Arrays.binarySearch(arr,1,i+1,arr[i]-k);
                if(l<0)l=-l-1;
                --l;
                int r = i-3;
                if(l==0)
                {
                    if(i>=3)
                    {
                        tree.setMin(1,1,n,i,1);
                    }
                }
                else if(l<=r)
                {
                    if(i==8)
                    {
                        int p = 0;
                    }
                    int min = tree.getMin(1,1,n,l,r);
                    tree.setMin(1,1,n,i,min+1);
                }
            }
            int res =  tree.getMin(1,1,n,n,n);
            res = res>=Inf? -1 : res;
            writer.WriteCase("Case ",cs,": ").WriteInt(res).WriteNewLine();
            System.gc();
        }
        writer.Dispose();
    }

    static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Reader() {
        }
        public Reader InitConsoleReading()
        {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
            return this;
        }
        public Reader InitFileReading(String filePath) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(filePath), 32768);
            tokenizer = null;
            return this;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    static class Writer {
        private BufferedWriter log;

        public Writer InitConsoleWriting()
        {
            log = new BufferedWriter(new OutputStreamWriter(System.out));
            return this;
        }
        public Writer InitFileWriting(String filePath) throws IOException {
            log = new BufferedWriter(new FileWriter(filePath));
            return this;
        }

        public Writer WriteInt(int inp) throws IOException {
            this.log.write(String.valueOf(inp));
            return this;
        }

        public Writer WriteChar(char inp) throws IOException {
            this.log.write(inp);
            return this;
        }
        public Writer WriteNewLine() throws IOException {
            return this.WriteChar('\n');
        }
        public Writer WriteStr(String str) throws IOException {
            this.log.write(str);
            return this;
        }

        public Writer WriteIntArray(int inp[], char delimChar) throws IOException {
            int len = inp.length;
            if(len>0)
            {
                log.write(String.valueOf(inp[0]));
                for(int i=1;i<len;i++)
                {
                    log.write(String.format("%c%s",delimChar,String.valueOf(inp[i])));
                }
            }
            return this;
        }
        public Writer WriteCharArray(char inp[], char delimChar) throws IOException {
            int len = inp.length;
            if(len>0)
            {
                log.write(String.valueOf(inp[0]));
                for(int i=1;i<len;i++)
                {
                    log.write(String.format("%c%s",delimChar,String.valueOf(inp[i])));
                }
            }
            return this;
        }
        //

        public Writer WriteStrArray(String inp[], char delimChar) throws IOException {
            int len = inp.length;
            if(len>0)
            {
                log.write(inp[0]);
                for(int i=1;i<len;i++)
                {
                    log.write(String.format("%c%s",delimChar,inp[i]));
                }
            }
            return this;
        }
        public Writer WriteCase(String prefix,int caseNo,String suffix) throws IOException {
            return this.WriteStr(String.format("%s%d%s",prefix,caseNo,suffix));
        }

        public Writer Dispose() throws IOException {
            this.log.flush();
            this.log.close();
            return this;
        }
    }
}