## Editorial for Bedao Grand Contest 04 - SUDI

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### Code mẫu

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+1;
int n;
ll a[N];
ll Mx[100001][20];
ll Mn[100001][20];
map<ll,int> trc;
ll res;
void init()
{
for (int i=1;i<=n;i++)
Mx[i][0]=Mn[i][0]=a[i];
for (int k=1; (1<<k)<=n; k++)
for (int i=1; i+(1<<k)-1<=n; i++)
{
Mx[i][k] = max(Mx[i][k-1],Mx[i+(1<<(k-1))][k-1]);
Mn[i][k] = min(Mn[i][k-1],Mn[i+(1<<(k-1))][k-1]);
}
}
ll getmx(int u,int v)
{
int k=log2(v-u+1);
return max(Mx[u][k],Mx[v-(1<<k)+1][k]);
}
ll getmn(int u,int v)
{
int k=log2(v-u+1);
return min(Mn[u][k],Mn[v-(1<<k)+1][k]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
freopen("SUDI.inp","r",stdin);
freopen("SUDI.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];

}
init();
for(int i=1;i<=n;i++)
{
int dau=trc[a[i]]+1,cuoi=i,giua;
int posl=i;
while(dau<=cuoi)
{
giua=(dau+cuoi)/2;
if(getmx(giua,i)==a[i])
{
posl=giua;
cuoi=giua-1;
}
else dau=giua+1;
}
dau=i,cuoi=n;
int posr=i;
while(dau<=cuoi)
{
giua=(dau+cuoi)/2;
if(getmx(i,giua)==a[i])
{
posr=giua;
dau=giua+1;
}
else cuoi=giua-1;
}
res+=1LL*(posr-i+1)*(i-posl+1)*a[i];

dau=trc[a[i]]+1,cuoi=i,giua;
posl=i;
while(dau<=cuoi)
{
giua=(dau+cuoi)/2;
if(getmn(giua,i)==a[i])
{
posl=giua;
cuoi=giua-1;
}
else dau=giua+1;
}
dau=i,cuoi=n;
posr=i;
while(dau<=cuoi)
{
giua=(dau+cuoi)/2;
if(getmn(i,giua)==a[i])
{
posr=giua;
dau=giua+1;
}
else cuoi=giua-1;
}
res-=1LL*(posr-i+1)*(i-posl+1)*a[i];
trc[a[i]]=i;
}
cout<<res;
return 0;
}