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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>

#define MAX 1000000000
#define MIN -1000000000

struct Sampler 
{
	uint32_t num_wrong;
	int32_t buff[3];
	bool rising;
	uint32_t cnt;
	const uint32_t fc;

	Sampler(bool rising, uint32_t first_check) 
		:num_wrong(0)
		,buff{0}
		,rising(rising)
		,cnt(0)
		,fc(first_check) {
	}
	
	void rotate(const int32_t val)
	{
		buff[0] = buff[1];
		buff[1] = buff[2];
		buff[2] = val;
		++cnt;
	}

	bool is_wrong() 
	{
		if (rising) 
		{
			// 1 2 1
			return buff[0] >= buff[1] || buff[1] <= buff[2];
		}
		else 
		{
			// 2 1 2
			return buff[0] <= buff[1] || buff[1] >= buff[2];	
		}
	}

	void fix() 
	{
		if (rising) 
		{
			// set to higher value
			buff[1] = buff[0] > buff[2] ? buff[0] : buff[2];
			buff[1] += 1;
		}
		else 
		{
			// set to lower value
			buff[1] = buff[0] < buff[2] ? buff[0] : buff[2];
			buff[1] -= 1;
		}
		++num_wrong;
	}

	bool should_check() 
	{
		if ((cnt > 1) && ((cnt % 2) == 1))
		{
			return true;
		}
		return false;
	}
	
	void update(const int32_t val) 
	{
		rotate(val);
		if (should_check())
		{
			if (is_wrong())
			{
				fix();
			}
		}
	}

	bool closing_wrong() 
	{
		if (rising) 
		{
			return buff[2] <= buff[1];
		}
		else 
		{
			return buff[2] >= buff[1];
		}
	}

	void close()
	{
		if ((cnt % 2) == 0)
		{
			if (closing_wrong()) 
			{
				++num_wrong;
			}
		}
	}


};

void prog_main(std::istream& in, std::ostream& out)
{
	int num = 0;
	in >> num;
	int32_t val;
	Sampler sR(true, 0);
	Sampler sF(false, 0);
	bool rising = true;
	for (int i = 0; i < num; i++)
	{
		in >> val;
		sR.update(val);
		sF.update(val);
	}
	sR.close();
	sF.close();
	uint32_t res = sR.num_wrong < sF.num_wrong ? sR.num_wrong : sF.num_wrong;
	out << res << "\n";
}

#ifndef TEST
int main(int argc, char* argv[])
{
	prog_main(std::cin, std::cout);
	return 0;
}
#endif