1
class Solution {
2
 public:
3
  using pi = pair<int, int>;
4
  int totalSteps(vector<int> &nums) {
5
    int N = nums.size();
6
    map<int, int> mp;
7
    vector<pi> del; // stores pairs of (previous id, toDelete id)
8
    for (int i = 0; i < N; ++i) {
9
      mp[i] = nums[i];
10
      if (i + 1 < N && nums[i] > nums[i + 1]) del.emplace_back(i, i + 1);
11
    }
12

13
    int ans = 0; // number of rounds
14
    while (!del.empty()) {
15
      ++ans;
16
      vector<pi> nxt;                      // pairs to delete in the next round
17
      for (auto [i, j] : del) mp.erase(j); // first, get rid of the required deletions
18
      for (auto [i, j] : del) {
19
        auto it = mp.find(i);
20
        if (it == end(mp) || next(it) == end(mp)) // if it's not in the map anymore,
21
          continue;                               // OR if it's the last element, skip it
22
        auto itn = next(it); // now compare against next element in the ordering
23
        if (it->second > itn->second)
24
          nxt.emplace_back(it->first,
25
                           itn->first); // add the (current id, toDelete id)
26
      }
27
      swap(nxt, del); // nxt is the new del
28
    }
29
    return ans;
30
  }
31
};