Minimum Card Deletions for Limited Score

Lanqi, the master card maker, invented a self‐service card game with a very peculiar set of rules. There are n cards numbered 1 to n with distinct weights a₁, a₂, …, a_n. Initially all cards are in the candidate pool. The rule‐generation phase begins by taking the card with the smallest number (card 1) into the hand. Then the following steps are repeated while the hand is nonempty:

1. Discard any card from the hand into the discard pile.
2. From the candidate pool, if there exists a card whose number and weight are both larger than that of the discarded card, pick the one with the smallest number and add it to the hand. In that case the discarded card and the chosen card are said to be swapped.
3. Then, from the candidate pool, if there exists a card whose number is larger than that of the discarded card but whose weight is smaller, pick the one with the smallest number and add it to the hand (and call them swapped) – if no such card exists, do nothing.

The rule‐generation phase is considered legal if and only if after it ends every card is in the discard pile, and furthermore a swap relationship is generated in a unique way (that is, each card’s set of swap‐partners under the above procedure is unique). In the formal game phase, one may start with an arbitrary card in hand and then repeatedly discard the card and replace it by one of its swap–partners (if available). Each such swap increases the score by 1.

After its release players complained that the maximum score (i.e. the longest chain of swaps) might be too high. They asked to remove some cards such that no matter which card is chosen as a start, the maximum score is at most k. To keep changes minimal, Lanqi further requires that after deletion for every preserved card the set of swap–partners (as generated in the rule–generation phase) is a subset of the original set. (Formally, if S is the set of swap–partners for a given card in the original game and T is the set after some removals, then T ⊆ S must hold.)

Your task is to compute the minimum number of cards you must delete to satisfy both the players’ and Lanqi’s requirements.

Note on the mechanics: For each card i (1 ≤ i ≤ n) define the following two candidate replacements (if they exist):

• g(i): the card with the smallest index j > i such that a_j > a_i.
• l(i): the card with the smallest index j > i such that a_j < a_i.

In the rule–generation phase, whenever a card is discarded its swap–partners are exactly those cards among { g(i), l(i) } which exist. In the formal game the player picks one swap–partner from those available. The maximum score equals the maximum length (number of swaps) that can be achieved following these edges. After some deletions the effective swap–partners of a preserved card i become the ones from { g(i), l(i) } which are still present. The invariant condition is that this resulting set is a subset of the original set.

Input/Output Note: You are given a single test case. It is guaranteed that under the original full–set the rule–generation phase is legal (so the swaps are unique) and that a swap chain (directed acyclic graph defined by the two pointers per card) is formed. Deletions remove nodes from this DAG; your goal is to delete as few nodes as possible so that the longest path (i.e. maximum swap chain length) in the remaining DAG is at most k.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 16, 0 ≤ k ≤ n – 1), representing the number of cards and the maximum allowed score respectively. The second line contains n distinct integers a₁, a₂, …, a_n representing the weights of the cards.

Note: Since the intended solution uses bitmask enumeration, n is guaranteed to be small.

outputFormat

Output a single integer – the minimum number of cards that must be deleted such that in the remaining cards the maximum possible score (the length of the longest swap chain) does not exceed k, and for each remaining card its set of swap–partners is unchanged (i.e. is a subset of the original).

sample

5 1
3 1 4 2 5

2