6040: YACS - IAI 2021年8月月赛乙组 T4 —— 栈的判断
[Creator : ]
Description
给定 $n$ 个数字，已知这些数字的入栈顺序为 $1,\ 2,\ \cdots,\ n$，给定一个出栈顺序 $a_1,\ a_2,\ \cdots,\ a_n$，请判断它是否是一个合法的出栈顺序。
Input
第一行：单个整数 $n$；
第二行：$n$ 个整数表示 $a_1,\ a_2,\ \cdots,\ a_n$。
第二行：$n$ 个整数表示 $a_1,\ a_2,\ \cdots,\ a_n$。
Output
如果合法，输出 Valid，否则输出 Invalid。
Constraints
对于 $30\%$ 的数据，$1\leq n\leq 20$；
对于 $60\%$ 的数据，$1\leq n\leq 2,000$；
对于 $100\%$ 的数据，$1\leq n\leq 100,000$；
对于 $60\%$ 的数据，$1\leq n\leq 2,000$；
对于 $100\%$ 的数据，$1\leq n\leq 100,000$；
Sample 1 Input
5
4 5 3 2 1
Sample 1 Output
Valid
1 入栈
2 入栈
3 入栈
4 入栈
4 出栈
5 入栈
5 出栈
3 出栈
2 出栈
1 出栈
2 入栈
3 入栈
4 入栈
4 出栈
5 入栈
5 出栈
3 出栈
2 出栈
1 出栈
Sample 2 Input
5
4 5 3 1 2
Sample 2 Output
Invalid