#P18844. [Croatian CPC2022] Egzotična Elegancija

[Croatian CPC2022] Egzotična Elegancija

Egzotična Elegancija

题目描述

给定一个长度为 nn 的整数序列。你可以在相邻元素之间切开它,将其分成若干个非空连续片段,然后重新排列这些片段的顺序。每个片段内部的元素顺序必须保持不变。

求最少需要切多少次,才能通过重新排列所得片段,拼接出一个非递减序列。

输入格式

第一行包含一个整数 nn。

第二行包含 nn 个正整数,表示给定的序列。

输出格式

输出一个整数,表示最少切割次数。

数据范围

  • 1≤n≤1061\le n\le10^6;
  • 序列中的每个数均不超过 2×1092\times10^9。

样例 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。