题目描述

给你一个长度为 $n$ 的数组 $nums$，你每次只能对连续的 $n-1$ 个数进行从小到大的排序，请输出你最少要排序多少次才能把数组排成有序的。

输入格式

两行，第一行输入一个整数 $n(3 \le n \le 5000)$，第二行输入长度为 $n$ 的数组 $nums(1 \le nums[i] \le 10^6)$。

输出格式

一行，输出最少需要的次数。

样例

4
2 6 8 5

1

6
4 3 1 6 2 5

2

5
50 20 30 40 10

3