← 返回题目列表

AtCoder · agc013_a

A. 排序数组

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个数组 A 长度 N。 您的任务是将其分为几个连续的子数组。 这里,获得的所有子数组必须按非降序或非升序排序。 至少需要划分多少个子数组 A 进入?

约束

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 每个 A_i 是一个整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N

输出

打印除法后子数组的最小可能数量 A.


示例输入 1

6
1 2 3 2 2 1

示例输出 1

2

一种最佳解决方案是将数组分为 [1,2,3] 和 [2,2,1].


示例输入 2

9
1 2 1 2 1 2 1 2 1

示例输出 2

5

示例输入 3

7
1 2 3 2 1 999999999 1000000000

示例输出 3

3