Language: C++

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define endl "\n"
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

#define N_MAX (1<<17)
#define INF 1000000000000LL

int nn_mx;
long long dat_mx[(2 * N_MAX) - 1];

void init_mx(int n1) {
  nn_mx = 1;

  while (nn_mx < n1)nn_mx *= 2;

  for (int i = 0; i < 2 * nn_mx - 1; i++) {
    dat_mx[i] = -INF;
  }
}

void update_mx(int k, long long a) {
  k += nn_mx - 1;
  dat_mx[k] = a;
  while (k > 0) {
    k = (k - 1) / 2;
    dat_mx[k] = max(dat_mx[k * 2 + 1], dat_mx[k * 2 + 2]);
  }
}

long long query_mx(int a, int b, int k, int l, int r) {
  if (r <= a || b <= l)return -INF;

  if (a <= l && r <= b) {
    return dat_mx[k];
  }
  else {
    long long vl = query_mx(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query_mx(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl, vr);
  }
}

  long long query(long long a, long long b){
    return query_mx(a,b,0,0,nn_mx);
  }

pair<ll,ll> mx_range(ll i, ll n){
  ll l, r;
  {
    long long low = 0;
    long long high = i;

    ll a = query_mx(i, i + 1, 0, 0, nn_mx);

    while (low < high) {
      long long mid = (high + low) >> 1;
      ll b = query_mx(mid, i + 1, 0, 0, nn_mx);
      if (b <= a) {
        high = mid;
      }
      else {
        low = mid + 1;
      }
    }
    l = low;
  }
  {
    long long low = i;
    long long high = n-1;

    ll a = query_mx(i, i + 1, 0, 0, nn_mx);

    while (low < high) {
      long long mid = (high + low + 1) >> 1;
      ll b = query_mx(i, mid + 1, 0, 0, nn_mx);
      if (b<=a) {
        low = mid;
      }
      else {
        high = mid - 1;
      }
    }
    r = low;
  }
  return pair<ll,ll>(l,r);
}

int main() {
	ll n;
	cin>>n;
	init_mx(n);
	vector<pair<ll,ll> > v;
	rep(i,0,n){
		ll a;
		cin>>a;
		v.pb(mp(a,i));
		update_mx(i,a);
	}
	sort(all(v));
	ll ans = 0;
	rep(i,0,v.sz-1){
		ll n1 = v[i].fi;
		ll index = v[i].se;
		pair<ll,ll> p = mx_range(index,n);
		ll l = p.fi;
		ll r = p.se;
		if(l>1){
			long long low = 0;
			long long high = l-2;
			
			while(low < high){
			  long long mid = (high + low) >> 1;
			
			  if(n1 < query(low,l-1)){
			    high = mid;
			  }
			  else{
			    low = mid + 1;
			  }
			}
			if(v[low]<n1){
			ans += n1*(r-low);
			}
		}
		if(r<n-1){
			long long low = r+1;
			long long high = n-1;
			
			while(low < high){
			  long long mid = (high + low + 1) >> 1;
			
			  if(n1 < query(r+1,mid+1)){
			    low = mid;
			  }
			  else{
			    high = mid - 1;
			  }
			}
			if(v[low]<n1){
			ans += n1*(low-l);
			}
		}
	}
	cout << ans << endl;
	return 0;
}




Compiler output:
a.cc: In function 'int main()':
a.cc:156:34: error: no match for 'operator<' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} and 'll' {aka 'long long int'})
  156 |                         if(v[low]<n1){
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   mismatched types 'const std::pair<_T1, _T2>' and 'll' {aka 'long long int'}
  156 |                         if(v[low]<n1){
      |                                   ^~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1760 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  156 |                         if(v[low]<n1){
      |                                   ^~
In file included from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/istream:40,
                 from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from a.cc:5:
/usr/include/c++/14/string_view:673:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator<(basic_string_view<_CharT, _Traits>, basic_string_view<_CharT, _Traits>)'
  673 |     operator< (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:673:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   'std::pair<long long int, long long int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/string_view:680:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator<(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)'
  680 |     operator< (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:680:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   'std::pair<long long int, long long int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/string_view:688:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator<(__type_identity_t<basic_string_view<_CharT, _Traits> >, basic_string_view<_CharT, _Traits>)'
  688 |     operator< (__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:688:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'long long int'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/basic_string.h:3874:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3874 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3874:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/basic_string.h:3888:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 3888 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3888:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  156 |                         if(v[low]<n1){
      |                                   ^~
/usr/include/c++/14/bits/basic_string.h:3901:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3901 |     operator<(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3901:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   mismatched types 'const _CharT*' and 'std::pair<long long int, long long int>'
  156 |                         if(v[low]<n1){
      |                                   ^~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68:
/usr/include/c++/14/tuple:2600:5: note: candidate: 'template<class ... _TElements, class ... _UElements> constexpr bool std::operator<(const tuple<_UTypes ...>&, const tuple<_Elements ...>&)'
 2600 |     operator<(const tuple<_TElements...>& __t,
      |     ^~~~~~~~
/usr/include/c++/14/tuple:2600:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::tuple<_UTypes ...>'
  156 |                         if(v[low]<n1){
      |                                   ^~
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from a.cc:9:
/usr/include/c++/14/bits/stl_vector.h:2089:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator<(const vector<_Tp, _Alloc>&, const vector<_Tp, _Alloc>&)'
 2089 |     operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:2089:5: note:   template argument deduction/substitution failed:
a.cc:156:35: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not deriv