The streets of a certain city form a very regular square grid. Some streets run north-south and others run east-west. Every intersection can be described by a pair of integer coordinates (i, j) in an obvious way. Because of the grid geometry, the distance you have to walk to get from one intersection (i1,j1) to another intersection (i2, j2) is |i1 − i2| + |j1 − j2|. For simplicity let us assume that the address of each resident of the city is some intersection point (i, j). The city wants to locate a hospital at some intersection in such a way as to minimize the total distance traveled by all residents to get to the hospital. Your task is to design an algorithm that takes as input a list of addresses (repeats allowed) of all n residents in the city , and return the location of the hospital that is optimal with respect to the city’s criterion above. Design such an algorithm that runs in O(n) time.