hanabi

Hanabi

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 C_i, where C_i 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:

1. Draw a card from the top of the deck
2. Play a card from her hand
3. Discard a card from her hand

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.

Input

The first line of the input will contain 2 integers separated by a space, N and R.

The second line will contain the numbers C₀,C₁,...,C_N-1, representing the cards in the deck. C₀ is at the top (ie the first card).

Output

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.

Limits

For all testcases:

• 1 ≤ N ≤ 100000
• 1 ≤ R ≤ N
• 1 ≤ C_i ≤ R
• For all i such that 1 ≤ i ≤ R, there exists a C_j such that i = C_j

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

Sample Input 1

6 5
3 4 5 1 2 1

Sample Output 1

4

Explanation

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.

Sample Input 2

7 4
3 4 2 1 4 1 3

Sample Output 2

2

Explanation

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.