Case 1: You would have to exchange at least 4 adjacent pairs.

Case 2: You would have to exchange at least 15 adjacent pairs.

Case 3: You would have to exchange at least 250015665837 adjacent pairs.

Case 4: You would have to exchange at least 499999500000 adjacent pairs.

Case 5: You would have to exchange at least 499999499998 adjacent pairs.

Case 6: You would have to exchange at least 0 adjacent pairs.