You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

塔子哥是一位火车车厢调度员。

这一天，一列带有 $n$ 个编号车厢的列车进站了，编号为 1~$n$ 。但是，这些车厢的编号并不是按从左到右递增的顺序，为了后面的工作方便展开，塔子哥想把火车调整成从左到右递增的顺序，即 [1，2，3，……n] ，但他只能进行一种操作：首先他要在火车中任意选择两个车厢取出。然后他将两个车厢中较大的放在火车的最右边，较小的放在火车的最左边。

他可以进行无限次这样的操作，他想知道最少需要多少次才能将火车调整为从左到右递增的顺序。

输入描述

第一行是数组的长度： $n$ . 第二行有n个数字 $p_i$ ($i=1,2,3, \dots ,n$) 表示从左到右的车厢编号。( $1≤n≤50000,1\leq p_i≤n$ )

输出描述

输出一个整数，表示最少需要操作多少次。

样例

样例输入

7
1 3 5 2 4 6 7

样例输出

3

样例说明

第一步选择5，3，第二步选2，6，第三步选1，7。