3. The city of San Juan commissions you to design a new bus system for Old San Juan which has n stops numbered 1, 2, . . . , n on the North-bound route (lets ignore the South-bound route). Commuters may begin their journey at any stop i and end at any other stop j > i. There are some obvious options:

(a) You can have a bus run from the southern-most point to the northernmost point as a traditional busline might run. The system would be cheap because it only requires n segments for the entire system. However, a person traveling from stop i = 0 to stop j = n must travel through all n segments. This system will be slow for that person.

(b) You can have a special express bus run from every point to every other destination. No person will every wait through any unnecessary segments no matter where they start and end. However, this system requires (n 2 ) segments and will be expensive.

Use a divide-and-conquer technique to design a bus system that uses (n log n) route segments and which requires a person to wait through at most 1 extra segment when going from any i to any j (as long as i j, i.e., we only consider North-bound routes for simplicity, and all buses run North). In other words, a commuter can travel from any i to any j by using at most 2 segments.