1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+7;
int A[N],dp[N][2];
void solve(){
	int n;
	cin>>n;
	for(int i = 1;i<=n;i+=1){
		cin>>A[i];
	}
	int res = n;
	for(int c = 0;c<2;c+=1){
		dp[1][0] = 0;
		dp[1][1] = 1;
		for(int i = 2;i<=n;i+=1){
			dp[i][0] = dp[i-1][1];
			dp[i][1] = min(dp[i-1][1],dp[i-1][0])+1;
			if ((i%2 && A[i]>A[i-1]) || (i%2==0 && A[i]<A[i-1])){
				dp[i][0] = min(dp[i][0],dp[i-1][0]);
			}
		}
		res = min(res,dp[n][0]);
		res = min(res,dp[n][1]);
		for(int i = 1;i<=n;i+=1){
			A[i] = -A[i];
		}
	}
	cout<<res<<endl;
}
signed main(){
	int tt = 1;
	while(tt--){
		solve();
	}
}