Maximum Width Ramp, an O(NlogN) solution

Problem is here: https://leetcode.com/problems/maximum-width-ramp/description/:

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:

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

There must be an O(N) solution to this problem, but I got an NLogN one (sorry). The idea is the following:

• Create a class called "Pair" which will have the value and index of the array
• Implement an IComparable interface (to be used in the Sort algorithm) in such a way that if the two values are the same, compare based on the index, otherwise compare based on the value
• After that do a linear scan keeping track of the smallest index all the way from 0..i-1, and check at element i whether the best width is greater than the max (using the smallest index var)

Not very fast by any stretch of the imagination. Would love to hear about an O(N) solution. Cheers, Boris

public class Solution
{
 public int MaxWidthRamp(int[] A)
 {
  Pair[] pairs = new Pair[A.Length];

  for (int i = 0; i < A.Length; i++)
  {
   pairs[i] = new Pair(A[i], i);
  }

  Array.Sort(pairs);

  int maxWidth = 0;
  int smallestIndex = pairs[0].index;

  for (int i = 1; i < pairs.Length; i++)
  {
   maxWidth = Math.Max(maxWidth, pairs[i].index - smallestIndex);
   smallestIndex = Math.Min(smallestIndex, pairs[i].index);
  }

  return maxWidth;
 }
}

public class Pair : IComparable
{
 public int val;
 public int index;

 public Pair(int val, int index)
 {
  this.val = val;
  this.index = index;
 }

 public int CompareTo(Object obj)
 {
  Pair p = obj as Pair;
  if (this.val == p.val) return this.index.CompareTo(p.index);
  return this.val.CompareTo(p.val);
 }
}