该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

研表究明,汉字的序顺并不定一能影阅响读,比方当你看完这句话后才发这现里的字全是乱的。

于是徐老师也依照这个结论，设计了一个新的概念 —— 错序数列

徐老师认为一个正整数数列，如果数列的第一项是数列中的最小值，最后一项是数列中的最大值，则这是一个 错序数列，例如数列 $[1,3,2,4],[1,1,5,6],[1,1,6,6]$ 都是错序数列，而 $[2,1,3],[2,5,4],[2,2,3,2]$ 则不是错序数列

现在徐老师会给定一个包含 $n$ 个正整数的数列 $a_1,a_2,a_3 \dots a_n$

在不允许修改序列中数字位置的情况下，请问这个序列最少可以分成几段数列，使得分割出的每个数列都是错序数列？

输入格式

输入第一行包含一个正整数 $n$ 表示序列长度

输入第二行包含 $n$ 个正整数 $a_1,a_2,a_3 \dots a_n$

输出格式

输出一个整数，表示最少分割的段数

数据范围

对于 $30\%$ 的数据，$n\le 500$

对于 $60\%$ 的数据，$n\le 5000$

对于 $100\%$ 的数据，$1 \le n \le 3\times 10^5, 1 \leq a_i \leq 10^9$

样例输入1

6
2 3 1 1 5 1

样例输出1

3

样例解释1

其中一种切割方案为：$[2,3],[1,1,5],[1]$

样例输入2

4
1 3 2 4

样例输出2

1

样例输入3

6
2 3 4 3 5 6

样例输出3

1