A Strange Sequence

Seunghyun built a sequence $B$ with the following rule.

• $B_i = S_i$ for $1 \le i \le N$
• $B_i$ is the number of distinct values among $B_1, B_2, \dots, B_{i-1}$ for $i > N$

Here $S$ is a sequence of length $N$ that Seunghyun thought up on his own.

Seunghyun wants to know the $M$th term of $B$. Write a program that computes that value for him.

The first line contains $N$, the length of the sequence $S$.

The second line contains $S_1, S_2, \dots, S_N$ in order, separated by spaces.

The third line contains $M$.

• $1 \le N \le 50000$
• $1 \le M \le 10^9$, and $M$ is a natural number
• every element of $S$ is an integer with $-1000000 \le S_i \le 1000000$

Print the $M$th term of the sequence $B$.

If $N = 4$ and $S = (2, 13, -7, 2)$, the first nine terms of $B$ are $2, 13, -7, 2, 3, 4, 5, 6, 7$.