CF 939 D. Nene and the Mex Operator

import java.io.*;
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
// reference taken from editorial and solution from : https://www.youtube.com/watch?v=lrX0a-kjIk8
public class D {
    List<int[]> op;
    void run() {
        int tc=ni();
        while(tc-->0) {
            int n=ni(), a[]=ni(n);
            op = new ArrayList<>();
            func(a);
            int s = 0;
            for(int v: a) s += v;
            ap(s(s), " ", s(op.size()), "\n");
            for(int indx[]: op) {
                for(int i: indx) ap(s(i+1), " ");
                ap("\n");
            }
            ap("\n");
        }
        out.println(sb);
        out.flush();
        out.close();
    }
    // in this we will create a sequence of 0, 1, 2, . . .
    void func2(int a[], int l, int r) {
        if(l == r) {
            if(a[l] != 0) {
                op.add(new int[]{l, l});
                a[l] = 0;
            }
            return;
        }
        // set all the elements to zero; we have to check individually each of them
        // bcz it might happen that already it contains 0
        func2(a, l+1, r);
        // check if its having a sequence of [r-l, r-l-1, . . . 1, 0] b/w {l, r},
        if(a[l] != r-l) {
            // if not then we have to set r-l to all bcz we have already [r-l-1, . . 1, 0] b/w {l+1, r}
            op.add(new int[]{l, r});
            for(int i = l; i <= r; i++) {
                a[i] = r - l;
            }
            // and here we call again {l+1, r} to create a sequence of [r-l-1, . . . 1, 0] b/w {l+1, r}
            func2(a, l + 1, r);
        }
    }
    void func(int a[]) {
        int n = a.length;
        int bstMask=0, bstSum=0;
        for(int i = 0; i < (1<<n); i++) {
            int tmp = 0;
            for(int l=0;l<n;l++) {
                // if 0 at ith bit means we have to replace all with length
                if((i&(1<<l)) == 0) {
                    int r = l;
                    while(r+1<n && (i&(1<<(r+1)))==0) ++r;
                    tmp += (r-l+1) * (r-l+1);
                    l=r;
                }
                else {
                    tmp += a[l];
                }
            }
            if(bstSum < tmp) {
                bstSum = tmp;
                bstMask = i;
            }
        }

        // debug(Integer.toBinaryString(bstMask), " ", s(bstSum));

        // now here we will generate all the operation needed to get bstSum from bstMask
        for(int l=0;l<n;l++) {
            if((bstMask&(1<<l)) == 0) {
                int r=l;
                while(r+1<n && (bstMask&(1<<(r+1)))==0) ++r;
                // to generate operation from {l, r}
                func2(a, l, r);
                op.add(new int[]{l, r});

                for(int i=l;i<=r;i++) {
                    a[i] = r-l+1;
                }
                l=r;
            }
        }
    }
    void funcX(int a[], int l, int r) {
        if(l > r) return;
        int s = 0;
        for(int i=l;i<=r;i++) s += a[i];
        // if sum of all elements b/w {l, r} is less than square of length
        // then try to create a sequence of 0, 1, 2, . . . to get max value
        if(s < (r - l + 1) * (r - l + 1)) {
            func2(a, l, r);
            // now after func2 it becomes like [r-l, r-l-1, . . . 1, 0]
            op.add(new int[]{l, r});
            // so after applying operation {l, r} all a[i] becomes (r - l + 1);
            for(int i=l;i<=r;i++) {
                a[i] = r - l + 1;
            }
        }
        // else here we will split based on the max position of element in array and do same thing recursively
        else {
            int mx = -1, pos = -1;
            for(int i=l;i<=r;i++) {
                if(mx < a[i]) {
                    mx = a[i];
                    pos = i;
                }
            }
            funcX(a, l, pos-1);
            funcX(a, pos+1, r);
        }
    }
    public static void main(String[] args)throws Exception {
        try {
            new Thread(null, new D()::run, "1", 1 << 26).start();
            // new Thread(null, new D("ONLINE_JUDGE")::run, "1", 1 << 26).start();
        } catch(Exception e) {}
    }

    FastReader sc=null;PrintWriter out = null;
    public D()throws Exception {
        sc = new FastReader(new FileInputStream("../input.txt"));
        out = new PrintWriter(new BufferedWriter(new FileWriter("../output.txt")));
    }
    public D(String JUDGE) {
        sc = new FastReader(System.in);
        out = new PrintWriter(System.out);
    }

    long ceil(long a, long b) {
        return (a + b - 1) / b;
    }

    StringBuilder sb = new StringBuilder();
    final int IMAX = Integer.MAX_VALUE;
    final int IMIN = Integer.MIN_VALUE;
    final long LMAX = Long.MAX_VALUE;
    final long LMIN = Long.MIN_VALUE;
    final int MOD = (int)1e9+7;

    void ap(String... str) {
        for(String s: str) sb.append(s);
    }
    void ap(Integer... arr) {
        for(Integer a: arr) sb.append(a);
    }
    void ap(Long... arr) {
        for(Long a: arr) sb.append(a);
    }
    void debug(String... str) {
        for(String s: str) System.out.print(s+" - ");
        System.out.println();
    }
    void debug(Integer... a) {
        for(Integer v: a) System.out.print(v+" - ");
        System.out.println();
    }
    void debug(Long... a) {
        for(long v: a) System.out.print(v+" - ");
        System.out.println();
    }
    void debug(int a[], Integer... b) {
        System.out.println(Arrays.toString(a));
        debug(b);
    }
    void debug(int a[][], Integer... b) {
        System.out.println(Arrays.deepToString(a));
        debug(b);
    }
    void debug(long a[], Long... b) {
        System.out.println(Arrays.toString(a));
        debug(b);
    }
    void debug(long a[][], Long... b) {
        System.out.println(Arrays.deepToString(a));
        debug(b);
    }
    String s(Long n) {
        return String.valueOf(n);
    }
    String s(Integer n) {
        return String.valueOf(n);
    }

    String ns() { return sc.next(); }
    int ni() { return sc.nextInt(); }
    long nl() { return sc.nextLong(); }
    char[] nc() {
        return ns().toCharArray();
    }
    char[][] nc(int n) {
        char c[][] = new char[n][];
        for(int i=0;i<n;i++) {
            c[i] = ns().toCharArray();
        }
        return c;
    }
    int[][] _ni(int n) {
        int a[][] = new int[n][];
        for(int i=0;i<n;a[i]=new int[]{i, ni()});
        return a;
    }
    int[] ni(int n) {
        int a[]=new int[n];
        for(int i=0;i<n;a[i++]=ni());
        return a;
    }
    long[] nl(int n) {
        long a[]=new long[n];
        for(int i=0;i<n;a[i++]=nl());
        return a;
    }

    int[][] ni(int n,int m) {
        int a[][]=new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                a[i][j]=ni();
        return a;
    }
    long[][] nl(int n,int m) {
        long a[][]=new long[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                a[i][j]=nl();
        return a;
    }
    int gcd(int a, int b) {
        return b==0?a:gcd(b,a%b);
    }
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;
        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res = res*1L*10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res *1L* sgn;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }
    }
}