You are given an unsorted array A of size n. You know that A is almost sorted, that is it contains at most m pairs of indices (i, j) such that i < j and A[i] > A[j]. To sort array A, you applied the Insertion Sort algorithm. Prove that it will take at most O(n + m) time.