public class CompStack1<A extends Comparable<A>> extends CompStack<A> {
    private int lastIncreasing = 1;
    public void push(A n) {
        checkInvariant();
        ((Object[])a)[tos]=n;
        tos++;
        if (tos>1 && lastIncreasing>=tos-1)
            if (((A)((Object[])a)[tos-2]).compareTo(n)<0)
                lastIncreasing = tos;
            else
                lastIncreasing = tos-1;
        checkInvariant();
    }
    public A pop() {
        checkInvariant();
        tos--;
        checkInvariant();
        return (A)(((Object[])a)[tos]);
    }
    public boolean isIncreasing() {
        boolean r = lastIncreasing>=tos;
        assert r == super.isIncreasing() : "lastincreasing="+lastIncreasing+" tos="+tos;
        return r;
    }
    // Invariante:
    // (forall i=1..min(tos,lastIncreasing)-1: a[i-1]<a[i]) &&
    // (lastIncreasing>=tos || a[lastincreasing-1]>=a[lastIncreasing])
    private void checkInvariant() {
        for (int i=1; i<Math.min(tos,lastIncreasing)-1; i++)
            assert ((A)((Object[])a)[i-1]).compareTo(((A)((Object[])a)[i]))<0;
        assert lastIncreasing>=tos || 
            ((A)((Object[])a)[lastIncreasing-1]).compareTo(((A)((Object[])a)[lastIncreasing]))>=0;
    }


    public void debug() {
        System.out.println("debug: "+this+" "+isIncreasingSlow());
        System.out.println("  tos = "+tos);
        System.out.println("  lastIncreasing = "+lastIncreasing);
    }
}