Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i. Find the maximum width of a ramp in A. If one doesn't exist, return 0.


Example 1:

Input: [6,0,8,2,1,5]
Output: 4

Explanation: 

The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7

Explanation: 

The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.


Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution in C++

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n=A.size();

        vector<pair<int,int>> my;
        for(int i=0; i<n; i++) my.push_back({A[i],i});
        sort( my.begin(), my.end());
        
        int max_width=0;
        int i=0;
        int j=1;
        while(j<n) {
            if (my[i].second<my[j].second) {
                max_width = max( max_width, my[j].second-my[i].second);
                j++;
            }
            else i++;
            
            if (i==j) j++;
        }
        
        return max_width;
    }
};