Problem 5089. -- [NWERC2017]Ascending Photo

5089: [NWERC2017]Ascending Photo

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 4  Solved: 3
[Submit][Status][Web Board]

Description

给定一个长度为n的序列h_1,h_2,h_3,...,h_n,你需要切k刀将其分成k+1段
然后你可以随意打乱这k+1段,但不能动每段内部。
求最小可能的k,使得你可以把它们从小到大排序。

Input

第一行包含一个正整数n(1<=n<=1000000)。
第二行n个正整数h_1,h_2,...,h_n(1<=h_i<=2*10^9),表示这个序列。

Output

输出一行一个整数,即最小的k。

Sample Input

11
3 6 12 7 7 7 7 8 10 5 5

Sample Output

4

HINT

Source

[Submit][Status]