AtCoder Grand Contest 024
翻译中…
Problem Statement
翻译中…
You are given a sequence $(P_1,P_2,...,P_N)$ which is a permutation of the integers from $1$ through $N$. You would like to sort this sequence in ascending order by repeating the following operation:
翻译中…
- Choose an element in the sequence and move it to the beginning or the end of the sequence.
翻译中…
Find the minimum number of operations required. It can be proved that it is actually possible to sort the sequence using this operation.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 2\times 10^5$$(P_1,P_2,...,P_N)$is a permutation of$(1,2,...,N)$.- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
P_1
:
P_N翻译中…
Output
翻译中…
Print the minimum number of operations required.
翻译中…
样例
Input #1
4
1
3
2
4
Output #1
2
For example, the sequence can be sorted in ascending order as follows:
- Move $2$ to the beginning. The sequence is now $(2,1,3,4)$.
- Move $1$ to the beginning. The sequence is now $(1,2,3,4)$.
Input #2
6
3
2
5
1
4
6
Output #2
4
Input #3
8
6
3
1
2
7
4
8
5
Output #3
5
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。