Заметим что максимум во всех подотрезках должен быть равен максимуму во всем массиве. Если максимумов меньше чем три, то ответ 0, так как всегда будет какой-то подотрезок без максимума. Иначе, будем перебирать левую и правую границу для второго подотрезка. Очевидно что L должно быть правее чем первое вхождение максимума и R должно быть левее последнего вхождения. Если мы хотим чтобы i был L то R может быть в промежутке от первого вхождения максимума после $$$i$$$ и последнего вхождения, то есть ответ выглядит так $$$\sum_{i = f + 1}^l (l - nxt_i)$$$ где $$$f$$$ — первое вхождение максимума, $$$nxt_i$$$ ближайше вхождение максимума правее $$$i$$$, а $$$l$$$ это последнее вхождение максимума.

//çalışan kazanır//

#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb push_back
#define S second
#define F first
#define all(x) x.begin(),x.end()
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)

int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}

const int N = 2e5 + 5;
const int INF = 1e18 - 1;
const int MOD = 998244353;

int n, a[N], cnt[5005], lst[N];

void solution () {
	cin >> n;
	int f = 0, l;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
	}
	int mx = *max_element (a + 1, a + n + 1);
	for (int i = 1; i <= n; ++ i) {
		if (a[i] == mx) {
			if (!f) f = i;
			l = i;
		}
	}
	int nxt = -1, res = 0;
	for (int i = l; i > f; -- i) {
		if (a[i] == mx) nxt = i;
		if (nxt != -1) res += (l - nxt);
	}
	cout << res;
	return;
}

signed main() {
	YOSIK();
	int T = 1;
	srand(time(0));
//	cin >> T;
	while (T --) solution ();	
  	return 0;

}

Нужно просто вывести Pow (2, n).

Заметим что мы может перебирать значения $$$a_i$$$ так как $$$a_i \le 5000$$$. Для каждого $$$x$$$ будем хранить сколько рах $$$x$$$ встречается в массиве. После будем перебирать $$$x, y$$$. Для определенных $$$x, y$$$ $$$z$$$ будет равно сумме $$$x$$$ и $$$y$$$, а ответ будет равен $$$cnt_x * cnt_y * cnt_z$$$ (Заметим что при $$$x = y$$$ ответ будет $$$cnt_x * (cnt_x - 1) / 2 * cnt_z$$$).

#include <iostream>
using namespace std ;

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int N = 1e5 + 1 ;

ll cnt[5001], a[N];
 

void solve() {
  ll n; cin >> n;
  for(int i = 1 ; i <= n ; i++) {
	cin >> a[i];
	cnt[a[i]] ++;
  }
  ll ans = 0 ;
  for(int i = 1 ; i <= 5000 ; i++) {
    for(int j = i ; j <= 5000 ; j++) {
      ll f = cnt[i], s = cnt[j];
      if (i == j) {
      	if (cnt[i] && i + j <= 5000 && cnt[i + j]) ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + j];
      }
      else if(i + j <= 5000 && cnt[i + j]) {
        ans += f * s * cnt[j + i] ;
      }
    }
  }
  cout << ans ;
}

int main() {
  ios::sync_with_stdio(false) ;
  cin.tie(0) ;
  int test = 1 ;
  // cin >> test ;
  while(test--) {
    solve() ;
  }
  
  return 0 ;
}

ответ будет $$$(n + 1) * (n + 1)$$$