水月与深蓝之树：最后的骑士

题目背景

这是离去的时刻，这是背离的时刻。

然而背离是理智，然而离去是众望。

曾经的荣耀只得在人们饭后嬉笑的嘴里苦痛地挣扎，

曾经的规则只得在人们戏谑酣醉的口中永恒的死去。

这是癫狂的时刻，这是不舍的时刻。

然而不舍却无力，然而癫狂非解放。

可怜的骑士希望人们铭记住美德与那骑士道的荣光，

可怜的骑士只能把疯癫与死亡作为自己惨淡的终场。

“杀死大海，播撒麦种！"

题目描述

最后的骑士向大海冲去。

海浪的高度是一个长度为 $n$ 的排列 $p_i$。

骑士可以向任意一段海浪区间冲刺。

紧接着，区间 $[l,r]$的海浪会立刻按照高度从小到大排序。

然而代价是海浪区间的长度，即 $r-l+1$ 的代价。

现在你可以让他进行若干次冲刺，直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序。

即对于 $1$ 到 $n$ 的每一个 $i$，都有 $p_i=i$。

求出代价之和的最小值。

输入格式

第一行给出一个整数 $n$。

第二行 $n$ 个整数，由空格隔开，代表排列 $p$ 中海浪高度的值。

输出格式

一行一个整数表示答案。

样例数据

样例一

3
1 3 2

2

样例二

4
3 2 1 4

3

提示

对于第一组样例，可选择区间 $[2,3]$ 进行排序。

对于第二组样例，可选择区间 $[1,3]$ 进行排序。

均可以证明选择方法最优。

【数据规模与约定】

对于 $100\%$ 的数据，$1\le n\le 10^5$。