**** Please implement in Java****

Magic index in an array a[1..n] is defined to be an index such that a[ i ] = i. Given an array of integers, write a recursive method to find the first magic index from left to right, if one exists, in the given array or otherwise return -1.

Here are some test cases. The first number is the size of the array.

Input1

6

-2 -2 -2 -2 -2 -1

Output1

-1

-------------------------------------------

Input2

5

-1 1 2 3 4

Output2

1