普及-⏱ 1000ms💾 256MB#P3160🏷️ 动态规划

题目描述

观光线路上有 $N$ 个观景台排成一列(编号 1~N),每个观景台有一个海拔。游客从左往右游览,规则如下:

  1. 所浏览的观景台编号必须严格递增;
  2. 相邻两个被浏览的观景台海拔不能相同;
  3. 一旦开始"下行"(海拔变低),之后就不能再"上行"(海拔变高)。

求最多能浏览多少个观景台。

输入格式

两行: 第一行整数 $N$($2 \le N \le 1000$); 第二行 $N$ 个整数,为各观景台海拔。

输出格式

一行,一个整数:最多能浏览的观景台数。

数据范围

$$2 \le N \le 1000$$

样例输入 #1
8
186 186 150 200 160 130 197 220
样例输出 #1
4
样例输入 #2
2
1 2
样例输出 #2
2