AA i; 1 <= i < n: A[i] <= A[i+1]