Shortest Non-subsequence

A subsequence is a sequence made by choosing some elements from another sequence while keeping their original order. For example, from S = [1, 5, 3, 2, 5, 1, 3, 4, 4, 2, 5, 1, 2, 3], choosing the 1st, 5th, 7th, and 10th elements gives the subsequence p = [1, 5, 3, 2].

Given a sequence S, find the minimum possible length of a sequence that cannot be made as a subsequence of S. Every element of that sequence must be an integer between 1 and k, inclusive.

The first line contains two integers n and k. n is the length of the sequence S, and k is the range of values that may appear in the sequence.

1 <= n <= 100000, 1 <= k <= 10000

Each of the next n lines contains one element of S in order. Every element is an integer between 1 and k, inclusive.

Print the shortest length of a sequence that is not a subsequence of S.

Every sequence of length 1 or 2 using integers from 1 to 5 appears as a subsequence of the given S. However, among sequences of length 3, [2, 2, 4] is not a subsequence of S.