The following segment of code is part of a program that uses insertion sort to sort a list A. for i = 2 to n

j = i while (j 2) and (A[j] < A[j 1]) exchange A[j] and A[j 1] j = j 1

What is the maximum number of times (considering all lists of n items that you could be asked to sort) the program makes the comparison A[j] < A[j 1]?

Describe as succinctly as you can those lists that require this number of comparisons.