<repo_name>tarangparikh/GeeksForGeeks<file_sep>/src/CountDistinctElementsInEveryWindow.java
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class CountDistinctElementsInEveryWindow {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;
    String solve(int[] data,int k,int n){
        int[] hash = new int[100005];
        StringBuilder sb = new StringBuilder();

        int distinct = 0;
        for(int i = 0;i<k;i++){
            if(hash[data[i]]++==0) distinct++;
            //sb.append(distinct+" "+i).append("\n");
        }
        sb.append(distinct).append(" ");
        for(int i = k,h=data.length;i<h;i++){
               if(hash[data[i-k]]--==1) distinct--;
               if(hash[data[i]]++==0) distinct++;
               sb.append(distinct).append(" ");
        }
        return sb.toString().trim();
    }
    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            int[] c = ints(2);
            int[] data = ints(c[0]);
            sb.append(solve(data,c[1],c[0])).append("\n");
        }
        writer.println(sb.toString().trim());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        CountDistinctElementsInEveryWindow object;
        if (local_system) object = new CountDistinctElementsInEveryWindow(new FileInputStream("input"), System.out);
        else object = new CountDistinctElementsInEveryWindow(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public CountDistinctElementsInEveryWindow(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/ds/ST.java
package ds;

public class ST {
    private int[] t;
    public ST(int size){
        this.t = new int[size<<1];
    }
    public void add(int i,int value){
        i += t.length / 2;
        t[i] += value;
        for (; i > 1; i >>= 1)
            t[i >> 1] = Math.min(t[i], t[i ^ 1]);
    }
    public int get(int i) {
        return t[i + t.length / 2];
    }
    public int min(int a, int b) {
        int res = Integer.MIN_VALUE;
        for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
            if ((a & 1) != 0)
                res = Math.min(res, t[a]);
            if ((b & 1) == 0)
                res = Math.min(res, t[b]);
        }
        return res;
    }
}
<file_sep>/src/Trie.java


import java.io.*;
import java.util.Arrays;


public class Trie {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;
    class TRIE {
        private final int SIZE = 26;
        private class Node{
            Node[] children;
            boolean isEnd;
            Node(){
                this.children = new TRIE.Node[SIZE];
                Arrays.fill(this.children,null);
                isEnd = false;
            }
        }
        private Node root;
        TRIE(){
            root = new Node();
        }
        void insert(String data){
            Node curr = this.root;
            for(int i = 0,h=data.length();i<h;i++){
                int index = data.charAt(i) - 'a';
                if(curr.children[index]==null) curr.children[index] = new TRIE.Node();
                curr = curr.children[index];
            }
            curr.isEnd = true;
        }
        boolean contains(String data){
            Node curr = this.root;
            for(int i = 0,h=data.length();i<h;i++){
                int index = data.charAt(i) - 'a';
                if(curr.children[index]==null) return false;
                curr = curr.children[index];
            }
            return curr.isEnd;
        }
    }

    int solve(String data,String search){
        TRIE trie = new TRIE();
        String[] tokens = data.split(" ");
        Arrays.stream(tokens).forEach(trie::insert);
        return trie.contains(search) ? 1 : 0;


    }
    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            getInt();
            String data = bf.readLine().trim();
            String search = bf.readLine().trim();
            sb.append(solve(data,search)).append("\n");
        }
        writer.println(sb.toString().trim());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        Trie object;
        if (local_system) object = new Trie(new FileInputStream("input"), System.out);
        else object = new Trie(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public Trie(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/MaximumCircularArraySum.java
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;

public class MaximumCircularArraySum {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    int solve(int[] data){
        int[] ddata = new int[(data.length<<1) + 1];
        int len = data.length;
        System.arraycopy(data,0,ddata,1,data.length);
        System.arraycopy(data,0,ddata,data.length+1,data.length);
        for(int i = 1,h=ddata.length;i<h;i++) ddata[i] += ddata[i - 1];
        //sb.append(Arrays.toString(ddata)).append("\n");
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for(int i = 1,h=data.length+1;i<h;i++){
            if (!deque.isEmpty()) while (!deque.isEmpty() && ddata[deque.peekFirst()] <= ddata[i]) deque.pollFirst();
            deque.addFirst(i);
        }
        //sb.append(deque).append("\n");
        int sum = data[0];
        for(int i = 0,h=data.length;i<h;i++){
            int max = ddata[deque.peekLast()];
            //sb.append(i).append(" ").append(max).append(" ").append(deque.peekLast()).append("\n");
            sum = Math.max(sum,max-ddata[i]);
            while (!deque.isEmpty()&&deque.peekLast()<=i+1) deque.pollLast();
            while (!deque.isEmpty()&&ddata[deque.peekFirst()]<=ddata[i+len+1]) deque.pollFirst();
            deque.addFirst(i+len+1);
        }
        return sum;

    }

    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            sb.append(solve(ints(getInt()))).append("\n");
        }
        writer.println(sb.toString().trim());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        MaximumCircularArraySum object;
        if (local_system) object = new MaximumCircularArraySum(new FileInputStream("input"), System.out);
        else object = new MaximumCircularArraySum(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public MaximumCircularArraySum(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/CircularTour.java
import java.io.*;
import java.util.Arrays;

public class CircularTour {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;
    int solve(int[] petrol,int[] distance){
        int n = petrol.length;
        int[] prefix = new int[(n<<1)];
        for(int i = 0;i<n;i++){
            prefix[i] = petrol[i] - distance[i];
            prefix[i+n] = prefix[i];
        }
        int sum = 0;
        int index = -1;
        int len = 0;
        for(int i = 0,h=prefix.length;i<h;i++){
            if(index > n-1){
                index = -1;
                break;
            }
            if(index == -1){
                if(sum + prefix[i] > 0){
                    index = i;
                    sum+=prefix[i];
                    len+=1;
                }
            }else{
                if(len==n) break;
                sum+=prefix[i];
                if(sum < 0){
                    index = -1;
                    sum = 0;
                }
            }
        }

        return index;
    }
    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            int n = getInt();
            int[] data = ints(n<<1);
            int[] petrol = new int[n];
            int[] distance = new int[n];
            for(int i = 0;i<n;i++){
                petrol[i] = data[i*2];
                distance[i] = data[i*2 + 1];
            }
            System.out.println(Arrays.toString(petrol)+"\n"+ Arrays.toString(distance));
            sb.append(solve(petrol,distance)).append("\n");
        }
        writer.println(sb.toString());
    }

    public static void main(String... args) throws IOException {
        long start_time = System.currentTimeMillis();
        CircularTour object;
        if (local_system)
            object = new CircularTour(Thread.currentThread().getContextClassLoader().getResourceAsStream("input"), System.out);
        else object = new CircularTour(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public CircularTour(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/OccurencesOf2AsAdigit.java
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class OccurencesOf2AsAdigit {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    void run() throws IOException {
        int[] data = new int[100005];
        for(int i = 1;i<data.length;i++){
            data[i] = data[i-1] + count(i);
        }
        int t = getInt();
        while (t-->0){
            sb.append(data[getInt()]).append("\n");
        }
        writer.println(sb.toString().trim());
    }
    int count(int n){
        int count = 0;
        while (n>0){
            int crr = n%10;
            count = crr == 2 ? count + 1 : count;
            n/=10;
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        OccurencesOf2AsAdigit object;
        if (local_system) object = new OccurencesOf2AsAdigit(new FileInputStream("input"), System.out);
        else object = new OccurencesOf2AsAdigit(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public OccurencesOf2AsAdigit(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/SortingElementsOfAnArrayByFrequency.java
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class SortingElementsOfAnArrayByFrequency {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    String sort(int[] data){
        int[][] hash = new int[11][2];
        for(int i = 0,h=data.length;i<h;i++){
            hash[data[i]][0] = data[i];
            hash[data[i]][1]++;
        }
        StringBuilder ssb = new StringBuilder();
        Arrays.sort(hash,(o1, o2) -> {
            if(o1[1]!=o2[1]) return Integer.compare(o2[1],o1[1]);
            return Integer.compare(o1[0],o2[0]);
        });
        //System.out.println(Arrays.deepToString(hash));
        for(int i = 0,h=hash.length;i<h;i++){
            if(hash[i][1]!=0)
            for(int j = 0,v=hash[i][1];j<v;j++){
                ssb.append(hash[i][0]).append(" ");
            }
        }
        return ssb.toString().trim();
    }

    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            sb.append(sort(ints(getInt()))).append("\n");
        }
        writer.println(sb.toString().trim());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        SortingElementsOfAnArrayByFrequency object;
        if (local_system) object = new SortingElementsOfAnArrayByFrequency(new FileInputStream("input"), System.out);
        else object = new SortingElementsOfAnArrayByFrequency(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public SortingElementsOfAnArrayByFrequency(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/IsBinaryNumberMultipleOf3.java
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class IsBinaryNumberMultipleOf3 {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    void run() throws IOException {
        int[][] state = new int[][]{{0,1},{2,0},{1,2}};
        int t = getInt();
        while (t-->0){
            String data = bf.readLine().trim();
            int curr = 0;
            for(int i = 0,h=data.length();i<h;i++){
                curr = state[curr][data.charAt(i) - '0'];
                //System.out.println(curr);
            }
            sb.append(curr == 0 ? 1 : 0).append("\n");
        }
        writer.println(sb.toString().trim());

    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        IsBinaryNumberMultipleOf3 object;
        if (local_system) object = new IsBinaryNumberMultipleOf3(new FileInputStream("input"), System.out);
        else object = new IsBinaryNumberMultipleOf3(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public IsBinaryNumberMultipleOf3(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/MergeKSortedLinkedLists.java
import java.util.Arrays;

class List{
    private class Node{
        Integer data;
        Node next;
        Node(){
            this.data = null;
            this.next = null;
        }

    }
    private Node last;
    private Node head;
    List(){
        this.head = new Node();
        this.last = this.head;
    }
    boolean isEmpty(){
        return this.head.data == null;
    }
    void add(int data){
        if (this.last.data != null) {
            this.last.next = new Node();
            this.last = this.last.next;
        }
        this.last.data = data;
    }
    public static List merge(List[] data){
        return merge(data,0,data.length-1);
    }
    public static List merge(List[] data,int start,int end){
        if(start == end) return data[start];
        int mid = (start + end) / 2;
        List p1 = merge(data,start,mid);
        List p2 = merge(data,mid+1,end);
        return merge(p1,p2);
    }
    public static List merge(List aa,List bb){
        Node a = aa.head;
        Node b = bb.head;
        Node temp = null;
        Node head = null;
        while (a!=null&&b!=null&&a.data!=null&&b.data!=null){
            if(a.data<=b.data){
                if(temp == null){
                    temp = a;
                    head = temp;
                }else {
                    temp.next = a;
                    temp = temp.next;
                }

                a = a.next;
            }else{
                if(temp == null){
                    temp = b;
                    head = temp;
                }else {
                    temp.next = b;
                    temp = temp.next;
                }
                b = b.next;
            }
        }
        while (a!=null&&a.data!=null){
            if(temp == null){
                temp = a;
                head = temp;
            }else {
                temp.next = b;
                temp = temp.next;
            }
            a = a.next;
        }
        while (b!=null&&b.data!=null){
            if(temp == null){
                temp = b;
                head = temp;
            }else {
                temp.next = b;
                temp = temp.next;
            }
            b = b.next;
        }
        if(head == null){
            head = a;
        }
        List send = new List();
        send.head = head;
        return send;
    }

    public void addAll(int[] data){
        Arrays.stream(data).forEach(this::add);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node temp = this.head;
        while (temp!=null&&temp.data!=null&&temp.next!=null){
            sb.append(temp.data);
            sb.append(" ");
            temp = temp.next;
        }
        if(temp.next==null){
            sb.append(temp.data);
        }
        sb.append("]");
        return sb.toString();
    }
}

public class MergeKSortedLinkedLists {
    public static void run(){
        List[] lists = new List[4];
        for(int i = 0,h=lists.length;i<h;i++){
            lists[i] = new List();
        }
        lists[0].addAll(new int[]{1,2,3});
        lists[1].addAll(new int[]{4,5});
        lists[2].addAll(new int[]{5,6});
        lists[3].addAll(new int[]{6,7});

        System.out.println(List.merge(lists));
    }

}
<file_sep>/src/LongestConsecutiveSubsequence.java
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class LongestConsecutiveSubsequence {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    int solve(int[] data){
        Arrays.sort(data);
        int mlen = 1;
        int clen = 1;
        int prev = data[0];
        //sb.append(Arrays.toString(data)).append("\n");
        for(int i = 1 , h = data.length ;i<h;i++ ){
            if(prev==data[i]) continue;
            if(prev == data[i]-1){
                clen++;
                mlen = Math.max(mlen,clen);
            }else{
                clen = 1;
            }
            prev = data[i];
        }
        return mlen;
    }
    int[] scaleLength(int[] data){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0,h=data.length;i<h;i++){
            max = Math.max(max,data[i]);
            min = Math.min(min,data[i]);
        }
        return new int[]{max,min};
    }
    int solve1(int[] data){
        int[] mm = scaleLength(data);
        int scale = mm[1];
        int[] hash = new int[mm[0] - mm[1] + 1];
        int len = data.length;
        for (int i = 0; i < len; i++) {
            int datum = data[i];
            hash[datum - scale]++;
        }
        int clen = 0;
        int mlen = 0;
        for(int h = hash.length,i=0;i<h;i++){
            if(hash[i]>0){
                clen++;
                mlen = Math.max(mlen,clen);
            }else{
                clen = 0;
            }
        }
        return mlen;
    }
    int solve2(int[] data,int n){
        int[] hash = new int[100005];
        int hash_len = 100005;
        for(int i = 0;i<n;i++) hash[data[i]] = 1;
        int mlen = 0;
        int clen = 0;
        for(int i = 0;i<hash_len;i++){
            if(hash[i]==1){
                clen++;
                mlen = clen > mlen ? clen : mlen;
            }else clen = 0;
        }
        return mlen;
    }

    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            int s = getInt();
            int d[] = ints(s);
            sb.append(solve2(d,s)).append("\n");
        }
        writer.println(sb.toString().trim());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        LongestConsecutiveSubsequence object;
        if (local_system) object = new LongestConsecutiveSubsequence(new FileInputStream("input"), System.out);
        else object = new LongestConsecutiveSubsequence(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public LongestConsecutiveSubsequence(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
<file_sep>/src/ds/TRIE.java
package ds;

import java.util.Arrays;

public class TRIE {
    private final int SIZE = 26;
    private class Node{
        Node[] children;
        boolean isEnd;
        Node(){
            this.children = new Node[SIZE];
            Arrays.fill(this.children,null);
            isEnd = false;
        }
    }
    private Node root;
    TRIE(){
        root = new Node();
    }
    void insert(String data){
        Node curr = this.root;
        for(int i = 0,h=data.length();i<h;i++){
            int index = data.charAt(i) - 'a';
            if(curr.children[index]==null) curr.children[index] = new Node();
            curr = curr.children[index];
        }
        curr.isEnd = true;
    }
    boolean contains(String data){
        Node curr = this.root;
        for(int i = 0,h=data.length();i<h;i++){
            int index = data.charAt(i) - 'a';
            if(curr.children[index]==null) return false;
            curr = curr.children[index];
        }
        return curr.isEnd;
    }
}
<file_sep>/src/MinimumCostOfRopes.java
import java.io.*;
import java.util.PriorityQueue;


public class MinimumCostOfRopes {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = true;

    public void solve(long[] data){
        PriorityQueue<Long> queue = new PriorityQueue<>();
        for(long d : data) queue.add(d);
        long count = 0;
        //sb.append(queue).append("\n");
        while (queue.size() > 1){
             long a = queue.poll();
             long b = queue.poll();
             queue.add(a+b);
             count+=(a+b);
        }
        sb.append(count).append("\n");
    }

    void run() throws IOException {
        int t = getInt();
        while (t-->0){
            solve(longs(getInt()));
        }
        writer.println(sb.toString());
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        MinimumCostOfRopes object;
        if (local_system)
            object = new MinimumCostOfRopes(new FileInputStream("input"), System.out);
        else object = new MinimumCostOfRopes(System.in, System.out);
        object.run();
        long end_time = System.currentTimeMillis();
        if (local_system) object.writer.println("Time : " + (end_time - start_time));
        object.close();
    }

    public MinimumCostOfRopes(InputStream in, OutputStream out) {
        this.writer = new PrintWriter(out);
        this.bf = new BufferedReader(new InputStreamReader(in));
        this.sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs(int size) throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() {
        this.writer.flush();
        this.writer.close();
    }
}
