#include <iostream> #include <algorithm> #include <vector> #include <map> using namespace std; long long v[1000005]; long long b[1000005]; long long calc(long long val,long long n) { long long minval=105,minprefix=105,minsuffix=105,p1=n+1,p2=-1; for(long long i=1;i<=n;i++) { if(v[i]<val) { b[i]=0; } else { b[i]=1; minval=min(minval,v[i]); } if(i>=2 && b[i]==0 && b[i-1]==1) { p1=min(p1,i); } if(i>=2 && b[i]==1 && b[i-1]==0) { p2=max(p2,i-1); } } if(p2==-1 || p1==n+1) { return 0; } long long cnt0=0; for(long long i=p1;i<=p2;i++) { if(b[i]==0) { cnt0++; } } for(long long i=1;i<=p1;i++) { if(b[i]==1) { minprefix=min(minprefix,v[i]); } } for(long long i=p2;i<=n;i++) { if(b[i]==1) { minsuffix=min(minsuffix,v[i]); } } long long suma=0; if(cnt0>=1) { suma=suma+minprefix+minsuffix+val-1; cnt0--; } if(cnt0>=1) { suma=suma+minval+val+val-1; cnt0--; } return suma+1ll*cnt0*(2*val+val-1); } signed main() { long long n,i,j,k,l,t,h,w,x,m,a,b; ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; for(long long i=1;i<=n;i++) { cin>>v[i]; } long long tot=0; for(long long val=1;val<=105;val++) { tot=tot+calc(val,n); } cout<<tot; return 0; }