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

Compile Errors

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

Subtask Score
1 0
2 30
3 70