#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#define ll long long
#define REP(I, A, B) for(int I = A; I <= B; I++)
#define RER(I, A, B) for(int I = A; I >= B; I--)

using namespace std;
const int MAXN = 1e6 + 5;
int n, a[MAXN], lmax[MAXN], rmax[MAXN], maxx;
ll los;
int read() {
	char ch = getchar(); int ans = 0;
	while(ch > '9' || ch < '0') ch = getchar();
	while(ch >= '0' && ch <= '9') ans = ans * 10 + (ch - '0'), ch = getchar();
	return ans;
}
int main() {
	freopen("rain.in", "r", stdin);
	freopen("rain.out", "w", stdout);
	n = read();
	REP(i, 1, n) a[i] = read();
	maxx = 0;
	REP(i, 1, n) lmax[i] = maxx, maxx = max(maxx, a[i]);
	maxx = 0;
	RER(i, n, 1) rmax[i] = maxx, maxx = max(maxx, a[i]);
	maxx = 0;
	REP(i, 1, n) {
		maxx = max(a[i], maxx);
		if(lmax[i] < a[i]) los += (ll)(a[i] - lmax[i]) * (i - 1);
		if(rmax[i] < a[i]) los += (ll)(a[i] - rmax[i]) * (n - i);
		los += a[i]; 
	}
	cout << (ll)maxx * n - los << endl;
	return 0;
} 
测试点 #1
Accepted
得分:100
用时:4 ms
内存:252 KiB

输入文件(rain1.in

3
1 3 3
输出文件(rain1.out
0
选手输出
0

测试点 #2
Accepted
得分:100
用时:4 ms
内存:252 KiB

输入文件(rain2.in

4
3 2 3 3
输出文件(rain2.out
1
选手输出
1

测试点 #3
Accepted
得分:100
用时:5 ms
内存:252 KiB

输入文件(rain3.in

4
4 2 4 3
输出文件(rain3.out
2
选手输出
2

测试点 #4
Accepted
得分:100
用时:5 ms
内存:252 KiB

输入文件(rain4.in

1000
49 153 935 533 261 672 206 697 168 560 745 847 354 837 200 561 494 571 152 406 733 585 297 5 272 40 222 570 392 770 614 319
<3768 bytes omitted>
输出文件(rain4.out
487807
选手输出
487807

测试点 #5
Accepted
得分:100
用时:7 ms
内存:252 KiB

输入文件(rain5.in

1000
841 478 902 907 730 65 103 947 844 544 596 946 116 994 140 434 556 958 131 933 5 328 594 387 51 479 744 189 584 723 629 13 
<3774 bytes omitted>
输出文件(rain5.out
493410
选手输出
493410

测试点 #6
Accepted
得分:100
用时:176 ms
内存:11900 KiB

输入文件(rain6.in

1000000
733559521 608025631 567700906 936145353 624081713 556992491 17064745 147569505 189563666 540190987 166894256 761940883 7
<9888949 bytes omitted>
输出文件(rain6.out
499597567421444
选手输出
499597567421444

测试点 #7
Accepted
得分:100
用时:191 ms
内存:11900 KiB

输入文件(rain7.in

1000000
953718300 54986646 304191666 735638078 816130121 369866885 889588169 842731984 114790813 123226927 502070030 827386192 7
<9889005 bytes omitted>
输出文件(rain7.out
499675611224705
选手输出
499675611224705

测试点 #8
Accepted
得分:100
用时:190 ms
内存:11900 KiB

输入文件(rain8.in

1000000
62821166 49574647 721516535 41308460 878072287 175102004 698032698 776791695 302257021 145143385 255174732 451235902 381
<9888637 bytes omitted>
输出文件(rain8.out
499875366161840
选手输出
499875366161840

测试点 #9
Accepted
得分:100
用时:203 ms
内存:12028 KiB

输入文件(rain9.in

1000000
694483080 721088486 321266954 171437663 527840336 259529357 536838427 699583976 565974475 249742863 942089808 396533007 
<9888363 bytes omitted>
输出文件(rain9.out
500040240311378
选手输出
500040240311378

测试点 #10
Accepted
得分:100
用时:173 ms
内存:11900 KiB

输入文件(rain10.in

1000000
523878176 11190867 830003008 880064918 498395069 91379857 86465627 334448169 437031561 202642344 185872183 817157039 647
<9888842 bytes omitted>
输出文件(rain10.out
499992400538086
选手输出
499992400538086