题目描述

告诉你一个长度为n的数列A，我们需要找到A的某个区间[L,R]的子序列B；并且子序列B满足条件当：

• [L,R]的元素升序排序后，A能成为一个升序排列的数组。

求解这样的子序列B的最短长度为多少？

输入格式

第一行一个数$n$ 然后n个数字$a_i$

输出格式

一个数字即b数组的长度

3
1 3 2

2

6
6 5 4 3 2 1

6

5
1 2 5 3 4

3

说明/提示

对于$10\%$的数据,保证a数组升序

对于$50\%$的数据,$1 \le a_i \le 10^5$

对于100%的数据,$1 \le n \le 10^5,-10^{18} \le a_i \le 10^{18}$