题目描述

你有一个队列 $A$，从队头到队尾分别有 $a_1,a_2,\dots,a_n$ 这 $n$ 个数字，且它们是 $1\sim n$ 的一个排列。你想通过一些寄存器把这些数字排序，寄存器共有 $k$ 个格子。你每步可以做以下操作之一：

• 把 $A$ 的队头数字弹出并输出。
• 把 $A$ 的队头数字弹出并放到寄存器的某个格子里。
• 把寄存器的某个格子里的数字输出。

你希望通过一系列操作使得你输出的数正好是 $1,2,3,\dots,n$。你需要计算出最少需要的寄存器的数量，也就是最小的 $k$。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，第 $i$ 个是 $a_i$。

输出格式

一行一个整数表示 $k$ 的最小值。

4
1 3 4 2

2

样例解释 1

一种可能的操作序列是：

• $1$ 直接弹出并输出
• $3$ 进入寄存器 1
• $4$ 进入寄存器 2
• $2$ 直接弹出并输出
• 输出寄存器 1 的 $3$
• 输出寄存器 2 的 $4$

一共用到了两个寄存器。

10
1 3 2 4 6 7 5 8 10 9

2

输入数据3/输出数据3

• sample3.in
• sample3.out

提示

对于 $100\%$ 的数据：$1\le n\le 10000$。

• 子任务 1（20 分）
  • $a_i=n-i+1$。
• 子任务 2（20分）
  • $30\%$ 的数据，$n\le 10$。
• 子任务 3（60分）
  • 无特殊限制