A flip in an array A[1:n] of numbers is a pair of indices (i, j) such that i < j and A[i] > A[j]. In other words, a flip is a pair of elements that are not in sorted order. Find an array of length n over the elements {1, . . . , n} that maximizes the number of flips, and prove that it is optimal.