Let A[0...n] be an array of n + 1 natural numbers not exceeding n. Let k < n be an integer such that the values of any two successive entries of A differ at most by k, i.e., |A[j] ? A[j + 1]| ? k for all j ? {0, . . . , n ? 1}. 1. Prove that there exist an index j such that |A[j] ? j| ? (k + 1)/2. 2. Given the number k, find an O(log n) divide and conquer algorithm that finds such an index.