Given an array \(A\) sorted in non-increasing order and an integer \(X\), determine whether \(X\) occurs in \(A\).

Input

The first line contains \(N\). The second line contains \(N\) integers \(A_i\) in non-increasing order. The third line contains \(X\).

The input satisfies:

• \(1 \le N \le 10^5\)
• \(|A_i|, |X| \le 10^9\)
• \(A_i \ge A[i+1] at every valid position.\)

Output

Print 1 if \(X\) occurs in A; otherwise, print 0.

Example

Input

5
9 7 7 3 1
7

Output

1