P3739.第2题-火车出站

1000ms

Difficulty: 5

所属公司 : 小米

算法与标签>双指针

题目内容

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

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

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

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

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

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

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

输入

5
1 3 5 2 4

输出

说明

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

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

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

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

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

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

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

输入

4
4 2 1 3

输出

-1

说明

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

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

输入

预期输出（选填）