题目描述

给定 $n$ 个数字，已知这些数字的入栈顺序为 $1,2,\cdots,n$，给定一个出栈顺序 $a_1,a_2,\cdots,a_n$，请判断它是否是一个合理的出栈顺序。

输入格式

• 第一行：单个整数 $n$；
• 第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$

输出格式

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

数据范围

• $1\leq a_i\leq n$
• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2,000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$；

样例数据

输入:

5
4 5 3 2 1

输出:

Valid

说明:

1 入栈
2 入栈
3 入栈
4 入栈
4 出栈
5 入栈
5 出栈
3 出栈
2 出栈
1 出栈

输入:

2
1 1

输出:

Invalid