Implement the following problem using the template listed below

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

import java.util.*;

class DriverMain{

public static void main(String args[]){

Scanner input = new Scanner(System.in);

int size = input.nextInt();

int a[] = new int[size];

for(int i = 0 ; i < size; i++){

a[i] = input.nextInt();

}

System.out.print(Quiz2.findMagicIndex(a));

}

class Quiz2{

public static int findMagicIndex(int[] a){

}

}

}