给定一个大小为 $N$ 的整数数组 $A$，洗牌（shuffle）操作定义如下：

• 首先，创建一个空的整数数组 $B$。
• 然后，当 $A$ 不为空时，移除 $A$ 的最左侧或最右侧元素，并将该值追加到 $B$ 的末尾。
• 当 $A$ 为空时，用 $B$ 替换 $A$ 并停止。

如果按照上图所示执行洗牌操作，数组 $A$ 的值变化如下：

$(34, 19, 5, 36, 4, 25, 12, 9) \to (9, 34, 19, 12, 25, 4, 5, 36)$。

令 $A_i$ 为数组 $A$ 的第 $i$ 个元素。当满足条件“若 $1 \le i < j \le N$，则 $A_i \le A_j$”时，称数组 $A$ 单调递增。

编写一个程序，给定一个大小为 $N$ 的整数数组 $A$，计算使数组 $A$ 变为单调递增所需的最小洗牌操作次数。

输入格式

第一行包含一个整数 $N$，表示数组 $A$ 的元素个数 ($1 \le N \le 3 \cdot 10^5$)。 第二行包含 $N$ 个整数 $A_1, \dots, A_N$，表示数组 $A$ 的初始值 ($1 \le A_i \le 10^9$)。

输出格式

输出使数组 $A$ 变为单调递增所需的最小洗牌操作次数。

样例

样例输入 1

3
2 2 5

样例输出 1

0

样例输入 2

6
1 5 8 10 3 2

样例输出 2

1