#P1464. [NWERC2017]Ascending Photo

    ID: 476 传统题 1000ms 256MiB 尝试: 20 已通过: 5 难度: 8 上传者: 标签>CF2400提高+/省选-离散化线性 DP最小值与次小值优化转移滚动数组链表

[NWERC2017]Ascending Photo

Description

给定一个长度为 nn 的序列 h1,h2,h3,…,hnh_1,h_2,h_3,\dots,h_n,你需要切 kk 刀将其分成 k+1k+1 段

然后你可以随意打乱这 k+1k+1 段,但不能动每段内部。

求最小可能的 kk,使得你可以把它们从小到大排序。

Input Format

第一行包含一个正整数n(1≤n≤106)n(1\leq n\leq 10^6)。

第二行n个正整数h1,h2,…,hn(1≤hi≤2×109)h_1,h_2,\dots,h_n(1\leq h_i\leq 2\times 10^9),表示这个序列。

Output Format

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

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