You are given two non-increasing 0-indexed integer arrays nums1​​​​​​ and nums2​​​​​​.

A pair of indices (i, j), where 0 &lt;= i &lt; nums1.length and 0 &lt;= j &lt; nums2.length, is valid if both i &lt;= j and nums1[i] &lt;= nums2[j]. The distance of the pair is j - i​​​​.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] &gt;= arr[i] for every 1 &lt;= i &lt; arr.length.

&nbsp;
Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).


Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: The valid pairs are (0,0), (0,1), and (1,1).
The maximum distance is 1 with pair (0,1).


Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
The maximum distance is 2 with pair (2,4).


&nbsp;
Constraints:


	1 &lt;= nums1.length, nums2.length &lt;= 105
	1 &lt;= nums1[i], nums2[j] &lt;= 105
	Both nums1 and nums2 are non-increasing.


class Solution:
    def maxDistance(self, n1: List[int], n2: List[int]) -> int:
        i = j = res = 0
        while i < len(n1) and j < len(n2):
            if n1[i] > n2[j]:
                i += 1
            else:
                res = max(res, j - i)
                j += 1
        return res
class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int max = 0;
        for (int i = 0; i < nums1.length; i++) {
            int r = nums2.length - 1;
            int l = i;
            int m = i;
            while (l <= r) {
                m = l + (r - l) / 2;
                if (nums1[i] > nums2[m]) {
                    r = m - 1;
                } else if (nums1[i] == nums2[m]) {
                    l = m + 1;
                } else {
                    l = m + 1;
                }
            }
            if (r < 0) {
                continue;
            }
            max = Math.max(max, r - i);
        }
        return max;
    }
}
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {

        reverse(nums2.begin(),nums2.end());
        int ans = 0;
        for(int i=0;i<nums1.size();++i){
            auto it = lower_bound(nums2.begin(),nums2.end(),nums1[i]) - nums2.begin(); //Finds first element greater than or equal to nums1[i]
            int j = nums2.size() - 1 - it; //Index of the found element in the original array
            if(i<=j) ans = max(ans,j-i); //Update distance
        }
        return ans;

    }
};
var maxDistance = function(nums1, nums2) {
    let i = 0, j = 0;
    
    let ans = 0;
    while (i < nums1.length && j < nums2.length) {
        // maintain the i <= j invariant
        j = Math.max(j, i);
        
        // we want to maximize j so move it forward whenever possible
        while (nums1[i] <= nums2[j]) {
            ans = Math.max(ans, j - i);
            j++;
        }
        
        // we want to minimize i so move it forward only to maintain invariants
        i++;
    }
    
    return ans;
};
Maximum Distance Between a Pair of Values