Language: C++

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;// number of elements
long long a[N];
map<pair<long long,long long>,int>m;
struct segment_tree
{
	long long tree[N*4];
	void setAr(long long x,long long l,long long r)//set values to all leaves
	{
		if(l==r)
		{
			tree[x]=l;
			return;
		}
		this->setAr(x*2,l,(l+r)>>1);
		this->setAr(x*2+1,(l+r)/2+1,r);
		if(a[tree[x*2]]>a[tree[x*2+1]])tree[x]=tree[x*2];
		else tree[x]=tree[x*2+1];
	}
	long long RMQ(long long x,long long l,long long r,long long L,long long R)
	{
		if(L<=l && r<=R)return tree[x];
		int f=0,ansl,ansr;
		if(L<=(l+r)/2)
		{
			ansl=this->RMQ(x*2,l,(l+r)>>1,L,R);
			f|=1;
		}
		if((l+r)/2<R)
		{
			ansr=this->RMQ(x*2+1,(l+r)/2+1,r,L,R);
			f|=2;
		}
		if(f==1)return ansl;
		if(f==2)return ansr;
		if(a[ansl]>a[ansr])return ansl;
		return ansr;
	}
}T;
int n;
long long find(long long l,long long r)
{
	long long ans;
	if(l>=r)return 0;
	if(m.find({l,r})!=m.end())return m[make_pair(l,r)];
	long long ma=T.RMQ(1,1,n,l,r),ma2,ma3;
	if(ma==l)ma2=T.RMQ(1,1,n,l+1,r);
	else if(ma==r)ma2=T.RMQ(1,1,n,l,r-1);
	else
	{
		ma2=T.RMQ(1,1,n,l,ma-1);
		ma3=T.RMQ(1,1,n,ma+1,r);
		if(a[ma3]>a[ma2])ma2=ma3;
	}
	ans=a[ma2]*(min(ma,ma2)-l+1)*(r-max(ma,ma2)+1);
	ans+=find(l,max(ma,ma2)-1)+find(min(ma,ma2)+1,r)-find(min(ma,ma2)+1,max(ma,ma2)-1);
	return m[make_pair(l,r)]=ans;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long  i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	T.setAr(1,1,n);
	cout<<find(1,n,n+1)<<'\n';
}


Compiler output:
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h: In instantiation of '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = int; _Predicate = __gnu_cxx::__ops::_Iter_equals_val<const int>]':
/usr/include/c++/14/bits/stl_algo.h:3850:28:   required from '_IIter std::find(_IIter, _IIter, const _Tp&) [with _IIter = int; _Tp = int]'
 3850 |       return std::__find_if(__first, __last,
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 3851 |                             __gnu_cxx::__ops::__iter_equals_val(__val));
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:69:12:   required from here
   69 |         cout<<find(1,n,n+1)<<'\n';
      |               ~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:2153:48: error: no matching function for call to '__iterator_category(int&)'
 2153 |                        std::__iterator_category(__first));
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:65:
/usr/include/c++/14/bits/stl_iterator_base_types.h:239:5: note: candidate: 'template<class _Iter> constexpr typename std::iterator_traits< <template-parameter-1-1> >::iterator_category std::__iterator_category(const _Iter&)'
  239 |     __iterator_category(const _Iter&)
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator_base_types.h:239:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_iterator_base_types.h: In substitution of 'template<class _Iter> constexpr typename std::iterator_traits< <template-parameter-1-1> >::iterator_category std::__iterator_category(const _Iter&) [with _Iter = int]':
/usr/include/c++/14/bits/stl_algobase.h:2153:34:   required from '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = int; _Predicate = __gnu_cxx::__ops::_Iter_equals_val<const int>]'
 2153 |                        std::__iterator_category(__first));
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:3850:28:   required from '_IIter std::find(_IIter, _IIter, const _Tp&) [with _IIter = int; _Tp = int]'
 3850 |       return std::__find_if(__first, __last,
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 3851 |                             __gnu_cxx::__ops::__iter_equals_val(__val));
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:69:12:   required from here
   69 |         cout<<find(1,n,n+1)<<'\n';
      |               ~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_iterator_base_types.h:239:5: error: no type named 'iterator_category' in 'struct std::iterator_traits<int>'
  239 |     __iterator_category(const _Iter&)
      |     ^~~~~~~~~~~~~~~~~~~