A long distance runner wants to carry only a single water bottle along the route and she can run k miles on one bottle of water. Before the race which is D miles long where D ≥ k, she is given a map of all n watering stops (i. e. mile markers of these stops). Design an effcient algorithm by completing the following function for determining where she should take a new bottle in order to make as few stops as possible. Estimate its time complexity. MinStops(A;D)
Input: Array A[0..n] where A[i] is distance of i-th watering stop, D is distance of race
Output: Sequence S of watering stops for the runner minimizing
number of stops; use append() function to add to S.