Rar the cat likes to play the card game hanabi, which means fireworks in Japanese. Hanabi is a co-op multiplayer game, but for the sake of this problem, the rules will be simplified.
Rar needs his mates to be of intelligence, so during his wedding ceremony, he gives Jacq the dinosaur a test involving his favourite game hanabi to determine if she is worthy
There is a deck of N cards. Each card has a value Ci, where Ci ranges from 1 to R (inclusive). Jacq has a hand size of H, so she can only hold H cards at any point in time. The objective of the game is to play the cards with values 1,2,..,R in that order, and nothing else.
Operations she is allowed to do:
Note that cards in the deck, and cards in the discard pile are not counted towards the hand size.
Determine the minimum H such that it is possible to complete the game.
The first line of the input will contain 2 integers separated by a space, N and R.
The second line will contain the numbers C0,C1,...,CN-1, representing the cards in the deck. C0 is at the top (ie the first card).
Output one line with a single integer, the minimal H such that it is possible to complete the game. It is guaranteed that it is always possible to complete the game.
For all testcases:
Subtask 1 (3%): N = R
Subtask 2 (7%): N ≤ 10
Subtask 3 (7%): R ≤ 10, N ≤ 1000
Subtask 4 (50%): N ≤ 1000
Subtask 5 (33%): No additional constraints
Subtask 6 (0%): Sample
6 5 3 4 5 1 2 1
Since card 3, 4, and 5 only appear once, it must be saved. So H must be at least 4. Jacq can play the 4th card (the 1), then draw the 5th card (the 2), play the 2, and then play the 3, 4 and 5 from her hand.
7 4 3 4 2 1 4 1 3
Construction for max 2 cards in hand:
Draw 3. Discard 3. Draw 4. Discard 4. Draw 2. Draw 1. Play 1. Play 2. Draw 4. Draw 1. Discard 1. Draw 3. Play 3. Play 4.