11917번 - 이상한 수열

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

• B_i = S_i (1 ≤ i ≤ N)
• B_i = B₁, B₂, ..., B_{i - 1} 에 있는 서로 다른 수의 개수 (N < i)

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

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

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

두 번째 줄에는 S₁, S₂, ..., S_N이 공백을 사이로 두고 차례대로 주어진다.

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

• 1 ≤ N ≤ 50,000
• 1 ≤ M ≤ 10⁹, M은 자연수
• 수열 S의 각 원소는 정수
• - 1, 000, 000 ≤ Si ≤ 1, 000, 000

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

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

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