You are given an array A (1-based indexing) of size N. You can remove upto N-1 elements from this array. You have to remove elements such that A[i] = i for all 1<=i<=N.

What is minimum number of elements you need to remove in order to satisfy given property. If not possible return -1.

Contraints:
1<=N<= 10^5
1<=Arr[i]<=10^5

e.g.:

1. Input array : [2,2], Output: -1 (not possible)
2. Input: [1,2], Output: 0 (already satify condition A[i] = i)
3. Input: [2,1,2], Output: 1 (delete first element so the array becomes [1,2] satisfying A[1] = 1 and A[2] = 2)

My Approach: Looks like we can find the answer by finding maximum length array that can be selected such that A[i] = i, let's say this we store in maxLen and then the final ans = N - maxLen.
Further this maxLen can be found by using DP.

Let me know your thoughts on my approach, also if anyone knows link to a related problem/article or about finding maxLen of array with A[i] = i please share that, would want to try with all the edge cases.
Also please upvote so that it stays on top