Consider a highway that is M miles long consisting of L lanes. At every mile, there exists a lane that is blocked from mile i to (just before) mile i+ 1. This information is recorded in an array LC[0, 1, . . . , M ? 1] of length M, where LC(i) = j means lane j is blocked from mile i to i+ 1. For example, LC = [1, 1, 3, 4, 1, 2, 2, 5, 4, 2, 2] describes the blockages on a 5-line highway of length 11. The objective is to find a route making the minimum number of lane changes. Changing from one lane into another one has a cost of 1. For the example given above, a solution with one lane change exists: start in lane 5 and change into lane 1 at mile 6 or later. It is not hard to see that more than one optimal solution can exist. (i) For M = 12 and L = 4 give an example of blocked positions that maximizes the number of lane changes. State the bound in terms of M and L and explain your answer. (ii) Consider now a greedy algorithm that starts in the lane having the farthest occurrence of a blockage and, whenever forced to switch lanes, it always switches into the lane having the farthest occurrence of a blockage. In the above example, greedy will start in lane 5 (since lane 5 has the farthest occurrence of the blockage) and at mile 6 change into lane 1 or lane 3 (these two lanes have no further blockages). Describe this greedy approach in pseudo-code and analyze its time performance in terms of M and L. Do not assume that either of these variables is a constant. Make sure to describe what data structures are used to select the next lane after a lane change. (iii) Prove that this greedy approach always generates a solution minimizing the number of lane changes