题目描述

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

输入格式

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

输出格式

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

数据范围

• 1≤ai​≤n
• 对于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 出栈

输入:

2
1 1

输出:

Invalid