이상한 수열 Batch Compilation commands

승현이는 아래와 같은 수열을 만들고 좋아서 히죽거리고 있다.

• $B_{i} = S_{i}$ ($1 \le i \le N$)
• $B_{i} = B_{1}, B_{2}, ..., B_{i - 1}$ 에 있는 서로 다른 수의 개수 ($N < i$)

여기서 $S$는 승현이가 혼자서 생각한 길이 $N$인 수열이다.

승현이는 수열 $B$의 $M$번째 항을 계산하고 싶어 한다. 하지만 이런 일은 승현이에게는 너무 쉽기 때문에 승현이는 귀찮아한다. 승현이 대신 수열의 $M$번째 항을 구하는 프로그램을 작성하여라.

입력 형식

첫 번째 줄에는 수열 $S$의 길이 $N$이 주어진다.

두 번째 줄에는 $S_{1}, S_{2}, ..., S_{N}$이 공백을 사이로 두고 차례대로 주어진다.

세 번째 줄에는 $M$이 주어진다.

출력 형식

수열 $B$의 $M$번째 항의 값을 출력한다.

부분문제

모든 채점 데이터에 대해,

• $N \ge 1$
• $M$은 자연수
• 수열 $S$의 각 원소는 정수
• $ - 1, 000, 000 \le S_{i} \le 1, 000, 000$

부분문제	점수	N	M
1	8	≤ 500	≤ N
2	24	≤ 500	≤ 103
3	30	≤ 50, 000	≤ 105
4	38	≤ 50, 000	≤ 109

입력과 출력의 예

입력

4
2 13 -7 2
9

출력

7

예제 설명

주어진 수열을 9번째 수까지 나타내면 아래와 같다.

2, 13, -7, 2, 3, 4, 5, 6, 7