Maximum Index Difference

Given an integer array A of size N, find the maximum difference between the indices j - i such that A[i] \(\neq\) A[j] and i < j. If no such pair exists, return -1.

More formally, given an array \(A[0 \ldots N-1]\), you are required to compute:

\(\max\{j-i \mid 0 \le i < j \le N-1 \text{ and } A[i] \neq A[j]\}\)

If there is no valid pair \((i,j)\) then output -1.

Example:

• For A = [1, 2, 2, 1, 3] and N = 5, the maximum index difference is 4.
• For A = [1, 1, 1, 1] and N = 4, there is no valid pair, hence the answer is -1.

inputFormat

The first line of input contains an integer N representing the number of elements in the array.

The second line contains N space-separated integers representing the array A.

outputFormat

Output a single integer representing the maximum index difference \(j-i\) such that A[i] \neq A[j] and i < j. If no such pair exists, output -1.

## sample

5
1 2 2 1 3

4

</p>