INPUT:
    arrab a, an array of any integers of length n
    array b, an array of any integers of length n
    
    OUTPUT:
    whether or not b is the sorted version of array a.

Is there some O(n) algorithm that I'm overlooking, or can't we decide the complexity of the optimal deterministic algorithm?