题目描述

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

输入格式

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

输出格式

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

5
4 5 3 2 1

Valid

样例解释 1

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

2
1 1

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$；