#include<iostream>
using namespace std;

int ans = 0;
int a[100005];

void solve(int start, int end) {
	if(start == end) return; //0
	int MIN = 100000;
	int index;
	for(int i = start; i < end; i++) {
		if(a[i] < MIN) {
			MIN = a[i];
			index = i;
		}
	}
	for(int i = start; i < end; i++) a[i] -= MIN;
	ans += MIN;
	solve(start, index);
	solve(index+1, end);
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	solve(0, n);
	cout << ans;
	return 0;
}

发现TLE了不可置信，明明是nlogn的复杂度，然后发现递增数列直接退化成n2了... 于是想了个O(n)的，然后就...WA了

//include...
//using...
int peak[50000]; int p = 0; // 存入峰的索引 p是个数
int valley[50000]; int v = 0; // 存入谷的索引 v是个数
int hill[100005];

int main() {
	long long ans = 0;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> hill[i];

	if(n == 1) ans = hill[0];
	else if(n == 2) ans = max(hill[0], hill[1]);
	else {

		// 存入峰和谷
		if(hill[0] > hill[1]) peak[p++] = 0;
		for(int i = 1; i < n-1; i++) {
			if(hill[i] >= hill[i-1] && hill[i] >= hill[i+1]) {
				peak[p++] = i;
				//峰不能相邻
				while(hill[i+1] == hill[i]) i++;
			}else if(hill[i] <= hill[i-1] && hill[i] <= hill[i+1]){
				valley[v++] = i;
				//谷不能相邻
				while(hill[i+1] == hill[i]) i++;
			}else;
		}
		if(hill[n-1] > hill[n-2]) peak[p++] = n-1;
		// 到此为止全部存入完毕

		for(int i = 0; i < p; i++) ans += hill[peak[i]];
		for(int i = 0; i < v; i++) ans -= hill[valley[i]];
	}
	cout << ans;
	return 0;
}