Envío 7177

Código

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mod = 1e9 + 7;
const string yes = "YES", no = "NO";

// Stack Array implementation

// - `top()`: Returns the element at the top of the stack
// - `push()`: Inserts an element at the top of the stack.
// - `pop()`: Takes out the element at the top of the stack and returns it.
// - `size()`: Returns an integer, the number of elements the stack currently stores.
// - `empty()`: You guessed it! Returns a boolean indicating if the stack is empty or not.

template<typename T> struct Stack{
  int _top, capacity;
  T* data;

  Stack(){
    _top = 0; 
    capacity = 16;
    data = new T[capacity];
  }

  bool empty(){
    return _top == 0;
  }

  int size(){
    return _top;
  }
  
  T top(){
    if (empty()){
      throw std::out_of_range("Stack is empty");
    }
    return data[_top - 1];
  }
  
  void push(T element){
    if (size() == capacity){
      // create new array
      capacity *= 2;
      T* new_arr = new T[capacity];
      // Copy elements from data to new array
      for (int i = 0; i < size(); i++){
        new_arr[i] = data[i];
      }

      std::swap(data, new_arr);
      delete [] new_arr;
    }
    data[_top++] = element; 
  }

  T pop(){
    if (empty()){
      throw std::out_of_range("Stack is empty");
    }
    return data[--_top];
  }
};


// Keeps two elements of X and Y type
template<typename X, typename Y> struct Pair{
  X first;
  Y second;
  Pair(X f, Y s){
    first = f;
    second = s;
  }
  Pair(){
  }
};

void solve(){
  int n;
  cin >> n;
  ll a[n];
  for (int i =0; i < n; i++){
    cin >> a[i];
  }
  // simulate with stack
  // mono-increasing stack
  Stack<Pair<ll,int>> s, s2;
  // prev element that is less than ith
  int prev[n], nxt[n];

  for (int i =0; i <n; i++){
    while (!s.empty() && s.top().first >= a[i]){
      s.pop();
    }
    prev[i] = (s.empty() ? i : ( -s.top().second + i - 1));
    s.push({a[i], i});
  }

  for (int i = n -1; i >= 0; i--){
    while (!s2.empty() && s2.top().first >= a[i]){
      s2.pop();
    }
    nxt[i] = (s2.empty() ? (n - i - 1ll) : (s2.top().second - i - 1));
    s2.push({a[i], i});
  }

  ll ans = 0;

  for (int i = 0; i < n; i++){
    ll x = (nxt[i] + prev[i] + 1) * a[i];
    ans = max(ans, x);
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

  #if LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif

  int tc = 1;
  // cin >> tc;

  for (int t = 1; t <= tc; t++){
    solve();
  }
}