Language: C++

#include <iostream>
#include <string>
#include <vector>
#include<limits>
#include<stack>
#include<queue>
#include<math.h>
#include <iomanip>

#define rep(i,n) for(auto i=0;i<(n);i++)
#define all(vs) (vs).begin(),(vs).end()
#define roundup(A,B) (A)/(B)+(A%B==0?0:1)
#define maximize(A,B) A=max((A),(B))
#define read(type,name) type name;cin>>name
#define ll long long

using namespace std;
template<typename T>
T MAX() { return numeric_limits<T>::max(); }

//二次元テーブル
template<typename T>
class Table {
public:
	Table(int height, int width, T value) {
		if (width < 0)throw std::exception("Width should be > 0");
		if (height < 0)throw std::exception("height should be > 0");
		this->wid = width;
		this->hgt = height;
		vs = new T[width * height];
		for (auto i = 0; i < width * height; i++)vs[i] = value;
	}
	Table(const Table& table) {
		hgt = table.hgt;
		wid = table.wid;
		vs = new T[hgt * wid];
		for (size_t i = 0; i < table.size(); i++) {
			vs[i] = table.vs[i];
		}
	}
	Table(Table&& table) {
		hgt = table.hgt;
		wid = table.wid;
		swap(vs, table.vs);
	}
	~Table() {
		if (vs)delete[] vs;
	}
	Table& operator=(const Table& table) {
		if (table == *this)return *this;
		this->wid = table.wid;
		this->hgt = table.hgt;
		if (vs)delete[] vs;
		vs = new T[wid * hgt];
		for (auto i = 0; i < wid * hgt; i++)vs[i] = table.vs[i];
	}
	Table& operator=(Table&& table) {
		wid = table.wid;
		hgt = table.hgt;
		swap(vs, table.vs);
	}
	inline T& at(int y, int x) {
		if (wid > x)throw out_of_range("x>width.");
		if (hgt > y)throw out_of_range("y>height.");
		return vs[x + y * wid];
	}
	int size()const { return wid * hgt; }
	int width()const { return wid; };
	int height()const { return hgt; };
	T* begin() { return vs; }
	T* end() { return vs + wid * hgt; }
	T& operator()(int y, int x) { return vs[x + y * wid]; }
	const T& operator()(int y, int x)const { return vs[x + y * wid]; }
private:
	int wid, hgt;
	T* vs;
};

struct MaxInfo {
	int first{ 0 };
	int second{ 0 };
	bool calculated{ false };
	static MaxInfo fromTry(int a, int b, int c) {
		if (a > b) {
			if (a > c) return { a,max(b,c),true };
			else return { c,a,true };
		} else {
			if (b > c)return { b,max(a,c),true };
			else return { c,b,true };
		}
	}
	static MaxInfo merge(MaxInfo a, MaxInfo b) {
		auto info = MaxInfo();
		if (a.first > b.first) return { a.first,max(a.second,b.first),true };
		else return { b.first,max(b.second,a.first),true };
	}
};

MaxInfo E_impl(const vector<int>& ns, Table<MaxInfo>& result, int l, int r) {
	if (result(l, r).calculated) return result(l, r);
	if (r - l == 1) {
		result(l, r) = { max(ns[l], ns[r]),min(ns[l],ns[r]),true };
		return result(l, r);
	}
	if (r - l == 2) {
		result(l, r) = MaxInfo::fromTry(ns[l], ns[l + 1], ns[l + 2]);
		return result(l, r);
	}
	// l=0  r=3 ->inter = 1
	auto inter = l + (r - l) / 2;
	result(l, inter) = E_impl(ns, result, l, inter);
	result(inter + 1, r) = E_impl(ns, result, inter + 1, r);
	result(l, r) = MaxInfo::merge(result(l, inter), result(inter + 1, r));
	return result(l, r);
}

void E() {
	read(int, n);
	auto ns = vector<int>(n);
	auto result = Table<MaxInfo>(n, n, {});
	for (auto i = 0; i < n; i++) cin >> ns[i];
	ll sum = 0;
	for (int l = 0; l < n-1; l++) {
		for (int r = l + 1; r < n; r++) {
			sum += E_impl(ns, result, l, r).second;
		}
	}
	cout << sum << endl;
}
int main() { E(); }

Compiler output:
a.cc: In instantiation of 'Table<T>::Table(int, int, T) [with T = MaxInfo]':
a.cc:120:39:   required from here
  120 |         auto result = Table<MaxInfo>(n, n, {});
      |                                              ^
a.cc:26:42: error: no matching function for call to 'std::exception::exception(const char [20])'
   26 |                 if (width < 0)throw std::exception("Width should be > 0");
      |                                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/exception:36,
                 from /usr/include/c++/14/ios:41,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/exception.h:67:5: note: candidate: 'constexpr std::exception::exception(std::exception&&)'
   67 |     exception(exception&&) = default;
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:67:15: note:   no known conversion for argument 1 from 'const char [20]' to 'std::exception&&'
   67 |     exception(exception&&) = default;
      |               ^~~~~~~~~~~
/usr/include/c++/14/bits/exception.h:65:5: note: candidate: 'constexpr std::exception::exception(const std::exception&)'
   65 |     exception(const exception&) = default;
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:65:15: note:   no known conversion for argument 1 from 'const char [20]' to 'const std::exception&'
   65 |     exception(const exception&) = default;
      |               ^~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/exception.h:62:5: note: candidate: 'std::exception::exception()'
   62 |     exception() _GLIBCXX_NOTHROW { }
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:62:5: note:   candidate expects 0 arguments, 1 provided
a.cc:27:43: error: no matching function for call to 'std::exception::exception(const char [21])'
   27 |                 if (height < 0)throw std::exception("height should be > 0");
      |                                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/exception.h:67:5: note: candidate: 'constexpr std::exception::exception(std::exception&&)'
   67 |     exception(exception&&) = default;
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:67:15: note:   no known conversion for argument 1 from 'const char [21]' to 'std::exception&&'
   67 |     exception(exception&&) = default;
      |               ^~~~~~~~~~~
/usr/include/c++/14/bits/exception.h:65:5: note: candidate: 'constexpr std::exception::exception(const std::exception&)'
   65 |     exception(const exception&) = default;
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:65:15: note:   no known conversion for argument 1 from 'const char [21]' to 'const std::exception&'
   65 |     exception(const exception&) = default;
      |               ^~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/exception.h:62:5: note: candidate: 'std::exception::exception()'
   62 |     exception() _GLIBCXX_NOTHROW { }
      |     ^~~~~~~~~
/usr/include/c++/14/bits/exception.h:62:5: note:   candidate expects 0 arguments, 1 provided