Given an array arr that represents a permutation of numbers from 1 to n.

You have a binary string of size n that initially has all its bits set to zero. At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1.

You are also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1's such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

&nbsp;
Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation: 
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.


Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation: 
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.


&nbsp;
Constraints:


	n == arr.length
	1 &lt;= m &lt;= n &lt;= 105
	1 &lt;= arr[i] &lt;= n
	All integers in arr are distinct.


class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        ans = -1
        if n == m: return m #just in case
        
#       make in "inverted" array with artificial ends higher then everything between

        sor= [0 for _ in range(n+2)]
        for i in range(n):
            sor[(arr[i])] = i+1 
        sor[0] = sor[n+1] = n+1
        
#       scan and see, if ones in the middle of space of length m appear 
#       before ones on its ends,
#       and find the latest of such spaces to disappear, if exists

        for i in range(1, n-m+2): 
            if all(sor[i-1]>sor[j] and sor[i+m]>sor[j] for j in range(i,i+m)):
                if min(sor[i-1]-1,sor[i+m]-1)>ans: ans = min(sor[i-1]-1,sor[i+m]-1) 
        return ans
class Solution {
    int[] par, size, count, bits;    
    // par: parent array, tells about whose it the parent of ith element
    // size: it tells the size of component
    // count: it tells the count of islands (1111 etc) of size i;
    // count[3] = 4: ie -> there are 4 islands of size 3
    
    public int find(int u) {
        if (u == par[u]) return u;
        par[u] = find(par[u]);
        return par[u];
    }
    
    public void union(int u, int v) {
        // union is performed over parents of elements not nodes itself
        int p1 = find(u), p2 = find(v);
        if (p1 == p2) return;
        
        // decrease the count of islands of size p1, p2
        count[size[p1]]--;
        count[size[p2]]--;
        
        // now merge
        par[p2] = p1;
        
        // adjust sizes
        size[p1] += size[p2];
        
        // adjust the count of islands of new size ie: size of p1
        count[size[p1]]++;
    }
    
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        par = new int[n + 1];
        size = new int[n + 1];
        count = new int[n + 1];
        bits = new int[n + 2];
        
        for (int i = 0; i < n; i++) {
            par[i] = i;
            size[i] = 1;
        }
        
        int ans = -1;
        for (int i = 0; i < n; i++) {
            int idx = arr[i];
            // set the bit
            bits[idx] = 1;
            // increase the count of islands of size 1
            count[1]++;
            
            if (bits[idx - 1] > 0) {
                union(idx, idx - 1);
            }   
            if (bits[idx + 1] > 0) {
                union(idx, idx + 1);
            }
            
            // check if island of size m exists
            if (count[m] > 0) {
                ans = i + 1;
                // as it is 1 based indexing
            }
        }
        return ans;
    }
}
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n=size(arr),ans=-1;
        vector<int>cntL(n+2),indL(n+2);
        for(int i=0;i<n;i++){
            int li=indL[arr[i]-1],ri=indL[arr[i]+1],nl=li+ri+1;
            indL[arr[i]]=nl;
            indL[arr[i]-li]=nl;
            indL[arr[i]+ri]=nl;
            cntL[li]--;
            cntL[ri]--;
            cntL[nl]++;
            if(cntL[m]>0)ans=i+1;
        }
        return ans;
    }
};
var findLatestStep = function(arr, m) {
    if (m === arr.length) return arr.length
    let bits = new Array(arr.length+1).fill(true), pos, flag, i, j
    for (i = arr.length - 1, bits[0] = false; i >= 0; i--) {
        pos = arr[i], bits[pos] = false
        for (j = 1, flag = true; flag && j <= m; j++) flag = bits[pos-j]
        if (flag && !bits[pos-m-1]) return i
        for (j = 1, flag = true; flag && j <= m; j++) flag = bits[pos+j]
        if (flag && !bits[pos+m+1]) return i
    }
    return -1
};
Find Latest Group of Size M