import java.util.Stack;

public class HistogramArea {
   /* public static int minVal(int[] arr, int i,int j){
        int min= Integer.MAX_VALUE;
        for(int k=i;k<=j;k++){
            min=Math.min(min,arr[k]);
        }
        return min;
    }
    public static int maxArea(@NotNull int[] arr){
        int max=Integer.MIN_VALUE, area=0;
        for(int i=0;i< arr.length;i++){
            for (int j = i; j < arr.length; j++) {
                int width=j-i+1;
                int length=minVal(arr,i,j);
                area=length*width;
                max=Math.max(area,max);
            }
        }
        return max;
    }*/
    public static void maxArea(int[] arr){
        int maxArea=0;
        int[] nsr =new int[arr.length];
        int[] nsl =new int[arr.length];
        Stack<Integer> s=new Stack<>();
        //next smaller right
        for (int i = arr.length-1; i >=0 ; i--) {
            while(!s.isEmpty()&&arr[s.peek()]>=arr[i]){
                s.pop();
            }
            if(s.isEmpty()) nsr[i]=arr.length;
            else nsr[i]=s.peek();
            s.push(i);
        }

        s=new Stack<>();
        //next smaller left
        for (int i = 0;i<arr.length;i++) {
            while(!s.isEmpty()&&arr[s.peek()]>=arr[i]){
                s.pop();
            }
            if(s.isEmpty()) nsl[i]=arr.length;
            else nsl[i]=s.peek();
            s.push(i);
        }

        for (int i = 0; i < arr.length; i++) {
            int h=arr[i];
            int w=nsr[i]-nsl[i]-1;
            int area=h*w;
            maxArea=Math.max(area,maxArea);
        }
        System.out.println(maxArea);
    }

    public static void main(String[] args){
        int[] arr={2,1,5,6,2,3};
        maxArea(arr);
    }
}

import java.util.Stack;

public class Parenthesis {
    public static boolean isValid(String str){
        Stack<Character> s=new Stack<>();
        int i=0;
        while(i<str.length()){
            if(str.charAt(i)=='('||str.charAt(i)=='{'||str.charAt(i)=='[') s.push(str.charAt(i));
            if(!s.isEmpty()){
                if((str.charAt(i)==')'&&s.peek()=='(')
                        ||(str.charAt(i)=='}'&&s.peek()=='{')
                        ||(str.charAt(i)==']'&&s.peek()=='[')){
                    s.pop();
                }
            }
            i++;
        }
        return s.isEmpty();
    }
    
    public static boolean duplicateParenthesis(String str){
        if(isValid(str)){
            Stack<Character> s=new Stack<>();
          for(int i=0;i<str.length();i++){
              if(str.charAt(i)==')'){
                  int count=0;
                  while(s.pop()!='(') count++;
                  if(count==0) return true;
              }
              else s.push(str.charAt(i));
          }
        }
        return false;
    }
    public static void main(String[] args){
        String str="((a+b)+((c+d)))";
        System.out.println(duplicateParenthesis(str));

    }
}

import java.util.Stack;
public class StockSpan {
    public static void stockSpan(int[] arr) {
        int[] span = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        span[0] = 1;
        s.push(0);
        for(int i = 1; i < arr.length; i++) {
            while (!s.isEmpty() && arr[i] > arr[s.peek()]) s.pop();
            if (s.isEmpty()) span[i] = i + 1;
            else span[i] = i - s.peek();
            s.push(i);
            }
        for (int j : span) {
            System.out.println(j + " ");
        }
        return;
    }
    public static void main(String[] args){
        int[] arr={100,80,60,70,60,85,100};
        stockSpan(arr);
    }
}

import java.util.*;

public class Stacks {
   /* static class Stack{
        static ArrayList<Integer> list= new ArrayList<>();
        public boolean isEmpty(ArrayList<Integer> list){
            return list.size()==0;
        }
        public int pop(ArrayList<Integer> list){
            if(isEmpty(list)) return -1;
            int x= list.get(list.size()-1);
            list.remove(list.size()-1);
            return x;
        }
        public void push(ArrayList<Integer> list, int n){
            list.add(n);
            return;
        }
        public int peek(ArrayList<Integer> list){
            if(isEmpty(list)) return -1;
            return list.get(list.size()-1);
        }
    }*/
   public static Stack bottomPush(Stack s,int n){
        if(s.isEmpty()) {
            s.push(n);
            return s;
        }
        int x= (int) s.pop();
        bottomPush(s,n);
        s.push(x);
        return  s;
    }

    public static String stringReverse(String str){
        Stack<Character> s= new Stack<>();
        int i=0;
        StringBuilder sb=new StringBuilder("");
        while(i<str.length()){
            s.push(str.charAt(i));
            i++;
        }
        i=0;
        while(i<s.size()){
            sb.append(s.pop());
        }
        return sb.toString();
    }

    public static Stack reverseStack(Stack s){
        if(s.size()==0) return s;
        int x= (int) s.pop();
        reverseStack(s);
        bottomPush(s,x);
        return s;
    }
    public static void main(String[] args){
        Stack <Integer> s=new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s);
        System.out.println(stringReverse("a"));
        System.out.println(reverseStack(s));
    }
}