2449: 栈的判断

题目描述

给定 n 个数字，已知这些数字的入栈顺序为 1,2,...,n，给定一个出栈顺序 a1,a2,...,an，请判断它是否是一个合法的出栈顺序。

输入格式

第一行：单个整数 n；
第二行：n 个整数表示 a1,a2,...,an

输出格式

如果合法，输出 Valid，否则输出 Invalid

数据范围

对于 30% 的数据，1≤n≤20；

对于 60% 的数据，1≤n≤2,000；

对于 100% 的数据，1≤n≤100,000；

样例数据

输入:

5

4 5 3 2 1

输出:

Valid

说明:

1 入栈

2 入栈

3 入栈

4 入栈

4 出栈

5 入栈

5 出栈

3 出栈

2 出栈

1 出栈

输入:

5

4 5 3 1 2

输出:

Invalid