Define a search algorithm called powSearch. Throughout, assume A is a 1-indexed sorted array of distinct integers. To search for an integer b in this array, we search the indices 2^{0}, 2^{1}, \ldots until we either reach the end of the array or A\left[2^{k}\right]>b. If at any point we get A\left[2^{k}\right]=b we stop and return 2^{k}. Once we have A\left[2^{k}\right]>b>A\left[2^{k-1}\right], we throw away the first 2^{k-1} elements of A, and recursively search in the same fashion. For example, for an integer which is at position 3 we will search the locations 1,2,4,3.
Define g(x) to be a function which returns how many (not necessarily distinct) indices we look at when calling powSearch with an integer b at position x in A. For example, g(3)=4. If A has length 64 , find