3. (22 pt) In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley algorithm is upper bounded by n2 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 n2, please give a way to construct the preference lists for n men and n women such that the Gale-Shapley algorithm will run for (n2) iterations. (For simplicity, you can assume that the algorithm always chooses the unmatched man with the smallest index at each iteration)