代码

#pragma GCC optimize("Ofast")
#include <iostream>
#include <stack>

using namespace std;
using tp = long long;


class Gen {
  unsigned nxt;

 public:
  Gen(unsigned _seed) : nxt(_seed) {}

  int get() { return nxt = nxt * 1103515245 + 12345; }
} gen(0);

struct SNode {
  tp val, id;

  SNode() = default;
  SNode(tp _val, tp _id) : val(_val), id(_id) {}
};

stack<SNode> s;

void add(tp val) {
  static tp cnt = 0;
  s.emplace(val, cnt++);
}

void add() {
  add(gen.get());
}

signed main() {
  tp n = 50000000, sum = 0, sed = 114514;
  gen = Gen(sed);
  add();
  for (tp i = 1; i < n; ++i) {
    tp val = gen.get();
    ++sum;
    if (s.size() && val > s.top().val) {
      s.pop();
      while (s.size() && val > s.top().val) {
        ++sum;
        s.pop();
      }
      sum += !s.empty();
    }
    add(val);
  }
  cout << sum;
  return 0;
}

评测结果