Card Trick

Problem Description

Aoki has a shuffled deck of cards which is a permutation of 1 to N. He wants to show off an impressive trick to his friends - dealing many cards in decreasing order!

However, Aoki only skilled enough to deal one of the top K cards of the deck. What is the longest sequence of cards of decreasing number he can deal?


The first line of input will contain two integers, N and K.

The next line contain N integers, which respresent the deck. The first integer is the card that is on the top of the deck. Each number is between 1 to N inclusive, and no two numbers are the same.


The output should contain one integer, the maximum number of cards Aoki can deal.


For all subtasks: 1 ≤ K ≤ N ≤ 500 000.

Subtask 1 (30%): K = 2.

Subtask 2 (70%): No additional constraints.

Subtask 3 (0%): Sample.

Sample Input

6 2
2 5 4 1 6 3

Sample Output



He can deal the cards 5, 4, 2, 1 in this order. After this, there is no card smaller than 1, so it's impossible.

Submitting .cpp to 'Card Trick'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 33
Your best score: 0
Source: Classic Problem (oolimry)

Subtask Score
1 0
2 30
3 70