Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM-ICPC亚洲区预选赛(北京赛区)游戏对抗邀请赛​正在报名中

Language:
The Cow Lineup
 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 5674 Accepted: 3372

Description

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row.Each cow is labeled with a number in the range 1...K (1 <= K <=10,000) identifying her breed. For example, a line of 14 cows might have these breeds:
`    1 5 3 2 5 1 3 4 4 2 5 1 2 3`

Farmer John's acute mathematical mind notices all sorts of properties of number sequences like that above. For instance, he notices that the sequence 3 4 1 3 is a subsequence (not necessarily contiguous) of the sequence of breed IDs above. FJ is curious what is the length of the shortest possible sequence he can construct out of numbers in the range 1..K that is NOT a subsequence of the breed IDs of his cows. Help him solve this problem.

Input

* Line 1: Two integers, N and K

* Lines 2..N+1: Each line contains a single integer that is the breed ID of a cow. Line 2 describes cow 1; line 3 describes cow 2; and so on.

Output

* Line 1: The length of the shortest sequence that is not a subsequence of the input

Sample Input

```14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3
```

Sample Output

```3
```

Hint

All the single digit 'sequences' appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear.

Source

[Submit]   [Go Back]   [Status]   [Discuss]