Problem A
BST Debugging

Some keys that might exist in a BST Via MaxPixel

Øyvind has recently implemented a binary search tree. However, there seems to be some problems with his implementation – some searches does not behave correctly. To debug his implementation he added a print statement whenever a key is examined in the tree, so he can find where it goes wrong.

Now the only problem is identifying which of these sequences of examined keys are invalid in a proper binary search tree. Can you write a program that checks if a sequence of keys examined in a search is valid?

Input

The first line consists of two integeres, $n$ ($1\le n\le 100000$), the number of keys examined in a given search, and $m$ ($-2^{31}\le m<2^{31}$), the key that is searched for. The next line contains $n$ space-separated keys (all $32$-bit signed integers) in the order they are examined by the search.

Output

Output “valid” if the sequence of keys examined is plausible in a correctly implemented BST, or “invalid” otherwise. There is no guarantee that the search tree is balanced, or that the search key exists in the tree.

5 10
20 15 5 9 11

valid

4 3
0 1 4 5

invalid

8 0
72 -500 32 16 8 7 -200 0

valid