解题思路

核心观察 按 1..n 依次进站，任一时刻能立刻出站的火车只可能是站内队列的两端：

• 最新到站的一端（原进站口=出站口1）；
• 最早到站的一端（直行口=出站口2）。 中间任意一辆在两个方向上都被挡住。

贪心 + 双端队列（Deque permutation）模拟

题目内容

有 $n$ 辆火车准备按照编号为 $1,2,…,n$ 的顺序进站，每辆火车有两种方式出站。第一种方式是从原进站口(出站口 $1$ )出站，第二种方式是沿着直行的轨道(出站口 $2$ )出站。

需要注意的是，只有当该火车在沿着出站口轨道的方向上没有其他火车时，该火车才能够出站，现在有一个出站序列，表示火车的出站顺序。

请问最多有多少辆火车是从原进站口(出站口 $1$ )出站的？

如果该出站序列不能表示某种出站的顺序，请输出 $-1$ 。

输入描述

第一行一个整数 $n(1≤n≤10^6)$ 表示火车的数量。

第二行 $n$ 个整数，表示出站序列，保证该序列为一个 $1$ 到 $n$ 的排列，即 $1$ 到 $n$ 出现且仅出现一次。

输出描述

一行一个整数，表示答案。

样例1

输入

5
1 3 5 2 4

输出

4

说明

第 $1$ 辆火车进站后立即从原进站口(出站口 $1$ )出站。

第 $2$ 辆火车进站后没有立即出站。

第 $3$ 辆火车进站后立即从原进站口(出站口 $1$ )出站。

第 $4$ 辆火车进站后没有立即出站。

第 $5$ 辆火车进站后立即从原进站口(出站口 $1$ )出站。

由于第 $2$ 辆火车在沿着原进站口出站的方向上存在着第 $4$ 辆火车，因此第 $2$ 辆火车只能沿着直行的轨道(出站口 $2$ )出站。

最后第 $4$ 辆火车从原进站口(出站口 $1$ )出站因此最多有 $4$ 辆火车从原进站口出站。

样例2

输入

4
4 2 1 3

输出

-1

说明

由于第 $4$ 辆火车最先出站，因此当第 $4$ 辆火车出站后，车站里还剩下 $1,2,3$ 辆火车。

由于第 $2$ 辆火车在沿着原进站口出站的方向以及沿着直行轨道的方向上分别存在着第 $3$ 辆火车以及第 $1$ 辆火车，所以此时第 $2$ 辆火车不可能出站，该序列不能表示一种出站序列，输出 $-1$ 。