1
class StockSpanner {
2
 public:
3
  stack<pair<int, int>> s; // val , index
4
  vector<int> prices;
5
  vector<int> res;
6
  StockSpanner() {}
7

8
  int next(int price) {
9
    prices.push_back(price);
10
    int n = prices.size();
11
    for (int i = n - 1; i < n; i++) {
12
      while (!s.empty() and s.top().first <= prices[i]) {
13
        s.pop();
14
      }
15
      if (s.empty()) {
16
        res.push_back(i - 0 + 1);
17
        s.push({prices[i], i});
18
      } else {
19
        auto it = s.top();
20
        res.push_back({i - it.second});
21
        s.push({prices[i], i});
22
      }
23
    }
24
    return res[n - 1];
25
  }
26
};