Envío 5299

Código

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  a.push_back(0);
  n++;

  stack<int> s;
  int64_t best = 0;
  for (int i = 0; i < n; ++i) {
    while (s.size() > 0 and a[s.top()] > a[i]) {
      int middle = s.top();
      int64_t height = a[middle];

      s.pop();
      int left = s.size() > 0 ? s.top() : -1; // index of first element to the left of middle that is strictly smaller
      int right = i; // index of first element to the right of middle that is strictly smaller

      int64_t width = right - left - 1;
      best = max(best, height * width);
    }
    s.push(i);
  }
  cout << best << endl;
  return 0;
}