404036 - 查找结点

有一棵二叉树,每个结点数据大于左子结点的数据,且要小于右子结点的数据。请根据该二叉树的特征,查找出要找的关键结点。

Input

第一行为一个整数n,表示有n个整数。 第二行为n个整数,为用数组表示法表示的二叉查找树。 第三行为一个整数k,表示要查找的结点。

Output

如果查找到结点,输出该数,否则输出“-1”。

Examples

Input

16
0 5 2 9 1 4 7 0 0 0 3 0 6 8 0 0
8

Output

8
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题