#P18844. [Croatian CPC2022] Egzotična Elegancija
[Croatian CPC2022] Egzotična Elegancija
Egzotična Elegancija
题目描述
给定一个长度为 的整数序列。你可以在相邻元素之间切开它,将其分成若干个非空连续片段,然后重新排列这些片段的顺序。每个片段内部的元素顺序必须保持不变。
求最少需要切多少次,才能通过重新排列所得片段,拼接出一个非递减序列。
输入格式
第一行包含一个整数 。
第二行包含 个正整数,表示给定的序列。
输出格式
输出一个整数,表示最少切割次数。
数据范围
- ;
- 序列中的每个数均不超过 。
样例 1
输入
4
1 2 2 3
输出
0
样例 2
输入
6
4 2 5 1 3 6
输出
5
样例 3
输入
7
5 5 6 7 1 2 3
输出
1
样例解释
样例 1 无须切割。
样例 3 可以切成 5 5 6 7 | 1 2 3,交换两个片段后得到 1 2 3 | 5 5 6 7。