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
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

long long L = 1<<16;
vector<int> LL (2*L);

void add(int a, int b){
	a += L;
	LL[a] = b;
	
	while(a /= 2){
		LL[a] += b;
	}
}
int query(int a, int b){
	a += L - 1;
	b += L + 1;
	int sum = 0;
	while(a/2 != b/2){
		if(a % 2 == 0) sum += LL[a+1];
		if(b % 2 == 1) sum += LL[b-1];
		b /= 2;
		a /= 2;
	}
	return sum;
}

int main(){
	int n; cin >> n;
	vector<int> L (n);
	for(auto&k : L)
		cin >> k;
	vector<bool> C (n+1);
	for(int i = 1; i < n-1; i++){
		if(L[i-1] > L[i] && L[i+1] > L[i])
			C[i] = 1;
		if(L[i-1] < L[i] && L[i+1] < L[i])
			C[i] = 1;
	}
	//for(auto k : C)
	//	if(k)cout << '1' << endl; else cout << '0' << endl;
	int licznik = 0; bool ost = -1;//kierunek na poczatku, 0 - dol, 1 - gora
	int suma = 0;
	for(int i = 1; i < n; i++){
		licznik = 0;
		if(L[i] < L[i-1])ost = 0;
		if(L[i] > L[i-1])ost = 1;
		for(; L[i] == L[i-1] && i < n; i++){
			licznik++; C[i-1] = 1;			
		}

		if(licznik){licznik++; //cout << licznik << endl;
			if(ost == -1 || i == n){
				suma += licznik/2; add(i-1, licznik/2); C[i-1] = 1;
			}else{
							bool ter;
			if(L[i] < L[i-1])ter = 0;
			if(L[i] > L[i-1])ter = 1;
			if(ter == ost){//kierunek taki sam
				if(licznik % 2 == 0){
					suma += licznik/2; add(i-1, licznik/2); C[i-1] = 1;
				}
			}else{//inny kierunek
				if(licznik % 2 == 0){
					continue;
				}else{
					suma += licznik/2; add(i-1, licznik/2); C[i-1] = 1;
				}
			}
			}
		}
			
	}
//for(auto k : C)
//	if(k)cout << '1' << endl; else cout << '0' << endl; cout << suma << endl;
	for(int i = 0; i < n-1; i++){
		if(!C[i] && !C[i+1]){
			C[i] = C[i+1] = 1; suma++; add(i, 1);
		}
	}
	C[0] = 0; C[n] = 0;

	vector<pair<int,int>> N (n+1);
	int naj = 0;
	for(int i = 1; i < n; i++)
		if(!C[i]){
			N[i].first = naj; naj = i;
		}
	naj = n;
	for(int i = n-1; i >= 1; i--)
		if(!C[i]){
			N[i].second = naj; naj = i;
		}	

	int sum1 = suma; int sum2 = suma;//sum1 - laczy z poprzednim, sum2 - laczy z kolejnym
	vector<bool> Vis (n+1);
	for(int i = 1; i < n; i++){
		if(!C[i] && !Vis[i]){
			sum1 += (N[i].second - i+1)/2 - query(i, N[i].second); Vis[N[i].second] = 1;
		}
	}
	for(int i = n-1; i >= 1; i--){
		if(!C[i]){
			sum2 += (i - N[i].first +1)/2 - query(N[i].first, i); C[N[i].first] = 1;
		}
	}
	//cout << sum1 << sum2 << endl;
	cout << min(sum1, sum2) << '\n';
	return 0;
}