Language: C++

#pragma once
#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;
};using namespace std;


/*
	3桁の数字からなる、重複を許す数字列はN^3パターンになる。O(1)
*/
void A() {
	read(int, i);
	cout << i * i * i << endl;
}

/*
 次の数字が連番である場合、追加でスコアが入る。そのため、直前の数字を記憶する必要がある。
 あとは情報を読み込んで配列を走査すればよい。空間量は今回削減できないと思われる。
*/
void B() {
	read(int, n);
	auto dishes = vector<int>(n);
	auto scores = vector<int>(n);
	auto bonus = vector<int>(n - 1);
	rep(i, n) cin >> dishes[i];
	rep(i, n) cin >> scores[i];
	rep(i, n - 1) cin >> bonus[i];
	auto prev = -1;
	int current;
	int result = 0;
	rep(i, n) {
		current = dishes[i];
		result += scores[current - 1];
		if (prev + 1 == current) result += bonus[prev - 1];
		prev = current;
	}
	cout << result << endl;
}

/*
 Bi>=max(Ai,A+1)が必ず満たされる。例えばB0はmax(A0,A1)以上の数字である。逆に言えば、A0とA1は最大でB0ということになる。
 となればA0とA1がともにB0であるとすれば最大である。一方で、B1がB0よりも小さい場合、A1はB1よりも小さくなければならないので
 A1をB0としてはならない。結局、Aiはmin(Bi-1,Bi)というのが最大になる。これを繰り返せばよい。O(n)の解法である。
*/
void C() {
	read(int, n);
	auto B = vector<int>(n - 1);
	rep(i, n - 1) cin >> B[i];
	int prevB = 100000000;
	int currentB;
	auto sum = 0;
	rep(i, n - 1) {
		currentB = B[i];
		sum += min(prevB, currentB);
		prevB = currentB;
	}
	//ラストはB１つで決まる。
	sum += currentB;
	cout << sum << endl;
}


/*											 
 LまたはRが連続する区間を調べ上げる。たとえばLLRRRRRRRRRRRRRRRLLについて、不幸な人間の数は
											 ^　             ^^  
矢印で示した3人である。ここで、Rで構成された区間をflipする。LLLLLLLLLLLLLLLLLLL
不幸な人は2人減ったことになる。ここで増減分はR区間の長さで変化しない。
LLRRLL		->Rの区間が2人以上 := -2
LLRLL		->Rの区間が1人だけ := -2

LとRを交換した状況を考える。

RRLLRR		->Lの区間が2人以上 := -2
RRLRR		->Lの区間が1人だけ := -2

やはり同じである。

またflipする区間が端っこである場合は増減が変化する

 LLRRLL  -> RRRRLL := -1(左端が救われた)
 LLRRLL  -> LLRRRR := -1(右端が不幸になったので2人減らすことはできなかった)
 
 RRLLRR  -> LLLLRR := -1(左端が不幸になったので2人減らすことはできなかった)
 RRLLRR  -> RRLLLL := -1(右端が救われた)


 以上を踏まえれば、端でない区間のflipを繰り返して不幸な人間を2人ずつ減らしていくことが最適な行為である。
 回数が余ってしまった場合は端を修正することでさらに減らすことができる。
 実際flipによって減った区間数が不幸な人間の減少数と一致する
 つまり最終的な幸福数は実はO(1)で求めることができ、必要なのは区間数を調べ上げるO(N)の計算が支配的になる。

 LLRR -> LLLL
 LLRR -> RRRR 
 RRLL -> RRRR
 RRLL -> LLLL

 どうやったって-1にしかならない。ありがたい。

 span数と不幸な人間の数は一意に対応するだろうか。
*/

void D() {
	read(int, n);
	read(int, k);
	int unhappy = 0;
	char prev; char c = '!'; cin >> prev;
	if (prev == 'L')unhappy++;
	for (size_t i = 1; i < n; i++) {
		cin >> c;
		if (c == 'L' && prev == 'R') unhappy += 2;
		prev = c;
	}
	if (c == 'R')unhappy++;//最後の人が右を向いていれば不幸
	for (size_t i = 0; i < k; i++) {
		if (unhappy > 2) unhappy -= 2;
		else if (unhappy == 2)unhappy--;
		else break;
	}
	cout << n - unhappy << endl;
}


/*
 考察1.
  Second[l,r]を求めるには、Second[l,r-1]での順位の変化を調べる必要がある。
  if(First[l,r-1]<N[r]){
	First[l,r]=N[r]
	Second[l,r]=First[l,r-1]
  }else if(Second[l,r-1]<N[r]){
	First[l,r]=First[l,r-1]
	Second[l,r]=N[r]
  }else{
	First[l,r]=First[l,r-1]
	Second[l,r]=Second[l,r-1]
  }

  しかしながら、これではSecond[l,0]からSecond[l,N]までを調べるだけでO(N)の時間が必要になってしまう。
  lを動かしながら同様の手続きをすればO(N^2)の時間がかかることは明白である。

 考察2.
  分割統治的な発想を考えてみる。配列を2つに分けてから統合する。
  N(L..R)についてN(L..r)とN(r+1...R)に分割してFirst[L,r]、Second[L,r]、First[r+1,R]、Second[r+1,R]を調べる。
  これを統合すればFirst[L,R]、Second[L,R]がすぐに計算できる。比較は最大で4つの数字のソートでしかない。
  大雑把に考えると計算量はO(NlogN)か。結果の統合コストが低いことが幸いしたか。

 考察コメント
 　あれ、1からNまでが一回ずつでるの？話変わるやんけ...
  実は答えって順番関係無く決まるんちゃう?

  "1 2 3" = 1 + 2 + 2
  "1 3 2" = 1 + 2 + 2
  "2 1 3" = 1 + 1 + 2
  "2 3 1" = 2 + 1 + 2
  "3 1 2" = 1 + 1 + 2
  "3 2 1" = 2 + 1 + 2

  パターンはあったけど、そこまで単純ではなかったな。
*/

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(); }
void F() {

}



Compiler output:
a.cc:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
a.cc: In instantiation of 'Table<T>::Table(int, int, T) [with T = MaxInfo]':
a.cc:274:39:   required from here
  274 |         auto result = Table<MaxInfo>(n, n, {});
      |                                              ^
a.cc:27:42: error: no matching function for call to 'std::exception::exception(const char [20])'
   27 |                 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:2:
/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:28:43: error: no matching function for call to 'std::exception::exception(const char [21])'
   28 |                 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