Language: C++

#include <bits/stdc++.h>
using namespace std;

int L;

vector<int> a;

struct I {
	int amax;
	unordered_map<int,int> pref, suff;
	bool tot_okay;
	int tot_num;
	I() {
		amax = 0;
		pref[0] = 1; suff[0] = 1;
		tot_okay = true;
		tot_num = 0;
	}
};

void level_up(I& v, int a){
	assert(a >= v.amax);
	while(v.amax < a){
		v.amax += 1;
		bool did_something = false;
		unordered_map<int,int> newpref, newsuff;
		for(auto q : v.pref){
			if(q.first == 0){
				newpref[0] += q.second;
			} else if(q.first < L){
				did_something = true;
			} else {
				did_something = true;
				newpref[q.first / L] += q.second;
			}
		}
		for(auto q : v.suff){
			if(q.first == 0){
				newsuff[0] += q.second;
			} else if(q.first < L){
				did_something = true;
			} else {
				did_something = true;
				newsuff[q.first / L] += q.second;
			}
		}
		v.pref = newpref;
		v.suff = newsuff;
		if(v.tot_okay){
			if(v.tot_num == 0){
			} else if(v.tot_num < L){
				did_something = true;
				v.tot_okay = false;
				v.tot_num = 0;
			} else {
				did_something = true;
				v.tot_num /= L;
			}
		}
		if(!did_something) break;
	}
	v.amax = a;
}

long long ans = 0;

vector<int> arr(const unordered_map<int, int> f){
	vector<int> a(f.size(), -1);
	for(pair<int,int> x : f){
		a[x.first] = x.second;
	}
	return a;
}

I combine(I& l, int a, I& r){
	level_up(l, a);
	level_up(r, a);
	assert(a == l.amax);
	assert(a == r.amax);
	I res;
	res.amax = a;
	res.pref = res.suff = {};
	if(l.tot_okay && r.tot_okay){
		res.tot_okay = true;
		res.tot_num = l.tot_num + 1 + r.tot_num;
	} else {
		res.tot_okay = false;
		res.tot_num = 0;
	}
	res.pref = move(l.pref);
	if(l.tot_okay){
		for(auto q : r.pref){
			res.pref[q.first + l.tot_num + 1] += q.second;
		}
	}
	res.suff = move(r.suff);
	if(r.tot_okay){
		for(auto q : l.suff){
			res.suff[q.first + r.tot_num + 1] += q.second;
		}
	}
	vector<int> la = arr(l.suff);
	vector<int> ra = arr(r.pref);
	long long cur = 0;
	cur += 1;
	long long tot = 0;
	int j = (int)ra.size();
	for(int i = 0; i < (int)la.size(); i++){
		while(j > 0 && (j-1) + 1 + i >= L){
			j -= 1;
			tot += ra[j];
		}
		cur += la[i] * tot;
	}
	ans += cur;
	return res;
}


int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n >> L;
	a.resize(n);
	for(int i = 0; i < n; i++) cin >> a[i];

	vector<int> b(n+2);
	vector<int> f(n+2);
	for(int i = 0; i <= n+1; i++){
		b[i] = i-1;
		f[i] = i+1;
	}
	vector<I> data(n+2);
	vector<pair<ll, int> > apos;
	for(int i = 0; i < n; i++){
		apos.push_back({a[i] * (1e9) + rand(), i+1});
	}
	sort(apos.begin(), apos.end());
	for(auto _x : apos){
		int x = _x.second;
		f[b[x]] = f[x];
		b[f[x]] = b[x];
		data[b[x]] = combine(data[b[x]], a[x-1], data[x]);
	}
	cout << ans << '\n';
}

Compiler output:
a.cc: In function 'int main()':
a.cc:134:21: error: 'll' was not declared in this scope
  134 |         vector<pair<ll, int> > apos;
      |                     ^~
a.cc:134:28: error: template argument 1 is invalid
  134 |         vector<pair<ll, int> > apos;
      |                            ^
a.cc:134:30: error: template argument 1 is invalid
  134 |         vector<pair<ll, int> > apos;
      |                              ^
a.cc:134:30: error: template argument 2 is invalid
a.cc:136:22: error: request for member 'push_back' in 'apos', which is of non-class type 'int'
  136 |                 apos.push_back({a[i] * (1e9) + rand(), i+1});
      |                      ^~~~~~~~~
a.cc:138:19: error: request for member 'begin' in 'apos', which is of non-class type 'int'
  138 |         sort(apos.begin(), apos.end());
      |                   ^~~~~
a.cc:138:33: error: request for member 'end' in 'apos', which is of non-class type 'int'
  138 |         sort(apos.begin(), apos.end());
      |                                 ^~~
a.cc:139:23: error: 'begin' was not declared in this scope
  139 |         for(auto _x : apos){
      |                       ^~~~
a.cc:139:23: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:166,
                 from a.cc:1:
/usr/include/c++/14/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/14/filesystem:53,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:200:
/usr/include/c++/14/bits/fs_dir.h:608:3: note:   'std::filesystem::__cxx11::begin'
  608 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
a.cc:139:23: error: 'end' was not declared in this scope
  139 |         for(auto _x : apos){
      |                       ^~~~
a.cc:139:23: note: suggested alternatives:
/usr/include/c++/14/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/14/bits/fs_dir.h:613:3: note:   'std::filesystem::__cxx11::end'
  613 |   end(recursive_directory_iterator) noexcept
      |   ^~~