An array A is given with N elements, where 3N. Also, assume that A[0]A[1] and A[N-2]A[N-1]. We say that an element A[k] is a local maximum if both A[k-1]A[k] and A[k]A[k+1], where 1kN-2. For example, there are six local maxima in the following array.

1

3

7

6

8

3

7

5

4

7

7

3

4

8

6

5

m m m m m m

Create a C++ program to find the index of one local maximum. For example, given the above array, your program could return 9, because A[9] is a local maximum. Note that any such array A should have at least one local maximum because of the boundary condition. Your task is to complete the function findLocalMaxIdx() which takes the array A[] and its size N as arguments and returns the index of one of the local maxima.

Required Time Complexity of your program: O(log₂N)