Description

假设一个数组,事先在你未知的情况下,以某一点分段有序排列。比如:(0,0,0,1,2,2,3 变成 0,0,1,2,2,3,0)。给定需要查找的数,在当前数组中查找,存在,返回 true,不存在,返回 false.

Format

Input

第一行输入数字 n(0<n<10000),接下来一行输入数组 A[n],数组 A[n]满足题目描述的条件,即分段有序。如:(2, 2, 0, 0, 1, 1);第三行输入要查找的 target 值。

Output

输出 true 或者 false。

Samples

7
1 2 2 2 0 1 1
0

true

Hint