INPUT:
arrab a, an array of length n of any integers
array b, an array of length n of any integers

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?