In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley algorithm is upper bounded by < n for n men and n women, since each man can only make n proposals. However, we haven't shown a lower bound on number of iterations. To show the lower bound is also in the order of n, please give a way to construct the preference lists for n men and n women such that the Gale-Shapley algorithm will run for (n) iterations. (For simplicity, you can assume that the algorithm always chooses the unmatched man with the smallest index at each iteration).