Maximum Rectangular Area in a Histogram

package com.company;

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader().InitConsoleReading();
        int kase = reader.nextInt();
        for(int ks=1;ks<=kase;ks++)
        {
            int n = reader.nextInt();
            int[] inp = new int[n];
            for(int i=0;i<n;i++)
            {
                inp[i]=reader.nextInt();
            }
            Stack<Integer> stk = new Stack<>();
            int[] L = new int[n];
            for(int i=0;i<n;i++)
            {
                int last = i;
                if(stk.empty() || inp[stk.peek()]<inp[i])stk.push(i);
                else
                {
                    while(!stk.empty() && inp[stk.peek()]>=inp[i])
                    {
                        last = stk.peek();
                        stk.pop();
                    }
                }
                L[i] = last;
                //System.out.println(i + " " + L[i]);
            }
            int res = 0;
            while(!stk.empty())stk.pop();
            for(int i=n-1;i>=0;i--)
            {
                int last = i;
                if(stk.empty() || inp[stk.peek()]<inp[i])
                {
                    stk.push(i);
                }
                else
                {
                    while(!stk.empty() && inp[stk.peek()]>=inp[i])
                    {
                        last = stk.peek();
                        stk.pop();
                    }
                }
                res = Math.max(res,(last - L[i]+1)*inp[i]);
            }
            System.out.println(res);

        }
    }

    private static <T> T swap(T... args) {
        // usage: z = swap(a, a=b, b=c, ... y=z);
        return args[0];
    }

    private static int swap(int a, int b) {
        return a;
    }

    static boolean next_permutation(int[] p) {
        for (int a = p.length - 2; a >= 0; --a)
            if (p[a] < p[a + 1])
                for (int b = p.length - 1; ; --b)
                    if (p[b] > p[a]) {
                        int t = p[a];
                        p[a] = p[b];
                        p[b] = t;
                        for (++a, b = p.length - 1; a < b; ++a, --b) {
                            t = p[a];
                            p[a] = p[b];
                            p[b] = t;
                        }
                        return true;
                    }
        return false;
    }

    static int gcd(int a, int b) {
        if (a < 0) a *= -1;
        if (b < 0) b *= -1;
        return b == 0 ? a : gcd(b, a % b);
    }

    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 String nextLine() throws IOException {
            return reader.readLine();
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}