通向宝可梦擂台之路！（贪心模拟）

https://cometoj.com/contest/42/problem/Ｈ

题目描述

小智接连得到两颗徽章，他非常自豪。小霞建议接下来去枯叶市，在那可以看见豪华客轮圣安妮。这种建议吸引不了小智，但是小刚却提醒小智枯叶市也有道馆。小智听闻立刻决定向枯叶市出发，路上有人建议他去向小明挑战。小明是位非常厉害的训练家，从未输过比赛。信心爆棚的小智决定去会会这位小明…...

在小明的私人擂台上，放了一个记分板，上面记录着小明的辉煌战绩，他已经98连胜了，对于小智的挑战小明信心满满，只派了一只穿山鼠就轻轻松松把小智的两只飞行系宝可梦都给打败了。小智很好奇小明的穿山鼠为什么这么强，于是他们跟着小明进入了他的帐篷，这个帐篷原来是一个大训练场，里面的每一只宝可梦都在努力训练，亲眼看到宝可梦和小明的相处情况之后，他们最终从对小明的训练感到非常佩服。

在小明打败想来偷宝可梦的火箭队之后，终于满了 100100 次连胜，于是小明带着穿山鼠踏上了获得徽章的旅行，小智也继续去寻找道馆。

在穿山鼠的训练中，有一种训练是把自己变成弹力球，从高处落下，降落到地面后会再弹起来，更严格来说，就是：

假设达到最高点的时间是 t_0, t_2, t_4, \ldots, t_{2*i}, t_{2*i+2}, \ldotst0​,t2​,t4​,…,t2∗i​,t2∗i+2​,…，落地的时间是 t_1, t_3, t_5, \ldots, t_{2*i+1}, t_{2*i+3}, \ldotst1​,t3​,t5​,…,t2∗i+1​,t2∗i+3​,…，也就是说，t_0t0​ 是训练开始的时间点，也当作是第一次在最高点的时刻，对于所有正奇数 jj， t_jtj​ 对应到所有的落地的时间点，对于所有的正偶数 kk， t_ktk​ 对应到所有的局部最高的时间点。并且对于所有非负整数 ii 都满足时间 [t_{2*i}t2∗i​, t_{2*i+1}t2∗i+1​] 内球的高度是严格递减，且时间 [t_{2*i+1}t2∗i+1​, t_{2*i+2}t2∗i+2​] 内球的高度是严格递增。

现在按照时间顺序给你 NN 个训练过程中不同的时间点穿山鼠的高度，请问穿山鼠至少接触到地面几次(地面高度为 00, 给的高度都不为 00)

输入描述

输入共两行。

第一行包含一个正整数 NN  (1 \le N \le 2 \times 10^51≤N≤2×105)。

第二行有 NN 个正整数 h_1, h_2, \ldots, h_Nh1​,h2​,…,hN​，代表按照时间顺序的穿山鼠的高度。(1 \le h_i \le 10^91≤hi​≤109)

输出描述

输出一行包含一個整数数字代表答案。

样例输入 1 

7
4 3 3 2 2 1 2

样例输出 1

3

样例输入 2 

1
7

样例输出 2

0

提示

下图的横轴是时间，纵轴是穿山鼠的高度，图中曲线是样例一的一个可能的落地次数最少的穿山鼠高度与时间的关系图。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int a[N];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	bool flag=true;
	int ans=0;
	a[0]=999999999;
	for(int i=1;i<=n;i++){
		if(flag){
			if(a[i]>=a[i-1]){
				flag=false;
				ans++;
			}
		}
		else{
			if(a[i]<=a[i-1]){
				flag=true;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}