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

public class RemoveMin {
    // It's OK if your solution doesn't have the static keyword
    public static int removeMin(Stack<Integer> s) {
        // TODO: Your solution here
        return -1;
    }


    public static void s2q (Stack<Integer> s, Queue<Integer> q) {
        while (!s.isEmpty()) {
            q.add(s.pop());
        }
    }

    public static void q2s(Queue<Integer> q, Stack<Integer> s) {
        while (!q.isEmpty()) {
            s.push(q.remove());
        }
    }

    // Testing code:
    public static void main(String[] args) {
        List<Case> cases = new ArrayList<>();
        cases.add(new Case("Spec example", stackOf(2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, -8, 4)));
        cases.add(new Case("Single value", stackOf(5)));
        cases.add(new Case("All negatives", stackOf(-5, -3, -10, -2)));
        cases.add(new Case("Spec example, no negative", stackOf(2, 8, 3, 2, 7, 3, 2, 42, 9, 3, 2, 7, 12, 2, 4)));
        cases.add(new Case("Mostly negatives repeating", stackOf(-1, 4, 6, 7, -4, -4, -4, -4, -4, 7, 9, 0, 100, -4)));
        cases.add(new Case("All positives", stackOf(5, 4, 7, 9, 3, 0)));
        cases.add(new Case("All large number", stackOf(99, 99, 99, 99, 99, 99, 99)));
        cases.add(new Case("Largest possible number", stackOf(Integer.MAX_VALUE)));

        int totalFailed = 0;
        for (Case c : cases) {
            totalFailed += c.test() ? 0 : 1;
            System.out.println(c);
        }
        System.out.println();
        System.out.println(totalFailed == 0 ? "All tests passed!" : totalFailed + " tests failed");

        if (totalFailed == 0) {
            System.out.println("Make sure to double-check that your solution abides by the following requirements before submitting a regrade request:");
            System.out.println("\t1. Only 1 Queue as aux storage");
            System.out.println("\t2. No additional data structures");
            System.out.println("\t3. Only uses the allowed S&Q methods");
        }
    }

    public static int solution(Stack<Integer> s) {
        Queue<Integer> q = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        while (!s.isEmpty()) {
            min = Math.min(s.peek(), min);
            q.add(s.pop());
        }
        while (!q.isEmpty()) {
            int val = q.remove();
            if (val != min) {
                s.push(val);
            }
        }
        s2q(s, q);
        q2s(q, s);
        return min;
    }

    public static Stack<Integer> stackOf(int... vals) {
        Stack<Integer> ret = new Stack<>();
        for (int i = 0; i < vals.length; i++) {
            ret.push(vals[i]);
        }
        return ret;
    }

    private static class Case {
        public String name;
        public Stack<Integer> s;
        public String reason;
        public boolean result;
        
        public Case(String name, Stack<Integer> s) {
            this.name = name;
            this.s = s;
            this.result = true;
        }

        public boolean test() {
            if (this.reason != null) {
                return result;
            }
            
            Stack<Integer> expected = Case.copy(s);
            Stack<Integer> actual = Case.copy(s);

            int expectedRet = RemoveMin.solution(expected);
            int actualRet = RemoveMin.removeMin(actual);

            this.reason = "";
            if (expectedRet != actualRet) {
                this.result = false;
                this.reason += "\n\tReturned value incorrect" +
                               "\n\t\tExpected: " + expectedRet +
                               "\n\t\tActual: " + actualRet;
            }
            if (!Case.getCounts(expected).equals(Case.getCounts(actual))) {
                this.result = false;
                this.reason += "\n\tResulting Stack has incorrect values" +
                               "\n\t\tExpected: " + expected +
                               "\n\t\tActual: " + actual;
            }
            return this.result;
        }

        public String toString() {
            if (this.reason == null) {
                return this.name + " - Untested";
            } else if (this.result) {
                return this.name + " - Passed";
            } else {
                return this.name + " - Failed" + this.reason;
            }
        }

        public static Stack<Integer> copy(Stack<Integer> s) {
            Stack<Integer> aux = new Stack<>();
            Stack<Integer> ret = new Stack<>();
            while (!s.isEmpty()) {
                aux.push(s.pop());
            }
            while (!aux.isEmpty()) {
                s.push(aux.peek());
                ret.push(aux.pop());
            }
            return ret;
        }

        public static Map<Integer, Integer> getCounts(Stack<Integer> s) {
            Stack<Integer> aux = new Stack<>();
            Map<Integer, Integer> counts = new TreeMap<>();
            while (!s.isEmpty()) {
                counts.put(s.peek(), counts.getOrDefault(s.peek(), 0) + 1);
                aux.push(s.pop());
            }
            while(!aux.isEmpty()) {
                s.push(aux.pop());
            }
            return counts;
        }
    }
}