The contest is ended. New submissions will be treated as correction submissions and will not be counted in the contest.

题目描述

玻璃管内有 $n$ 个小球，编号为 $1\sim n$，从左往右第 $i$ 颗球编号为 $p_i$。

接下来你每次从管左边或右边取出一个球，直到把所有球取完，设你第 $i$ 次取到的球编号为 $q_i$。

称满足 $i<j<k,q_i<q_j<q_k$ 的三元组 $(i,j,k)$ 数量为 $q$ 的整齐度。当然，根据题目《论整齐度与美观》，你需要求出 $q$ 的最小整齐度。

输入格式

输入的第一行有一个正整数 $n$。

第二行有 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，其中 $1\sim n$ 各出现一次。

输出格式

输出一行一个自然数，表示最小整齐度。

样例 #1

样例输入 #1

7
1 5 7 4 3 2 6

样例输出 #1

1

样例 #2, #3

点我下载大样例

两个样例分别满足测试点 $6,20$ 的限制。

提示

【样例解释】

按照 $6,1,5,7,4,3,2$ 的顺序取，只有 $q_2<q_3<q_4$ 是整齐的，所以输出 $1$。

可以证明没有整齐度更小的方案，但是方案是否唯一，我不知道。

【数据规模】

• 性质 A：存在 $x$ 使得 $p_1,p_2,\ldots,p_x$ 单调递减，$p_x,p_{x+1},\ldots,p_{n}$ 单调递增。

对于全部数据，保证 $3\le n\le 2\times 10^4$。