uCoder | 1218 | Nível: 6 | Tempo Limite: 4
Mário
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2014
Mário é dono de uma empresa de guarda-volumes, a Armários a Custos Moderados (ACM). Mário conquistou sua clientela graças à rapidez no processo de armazenar os volumes. Para isso, ele tem duas técnicas:
• Todos os armários estão dispostos numa fila e são numerados com inteiros positivos a partir de 1. Isso permite a Mário economizar tempo na hora de procurar um armário;
• Todos os armários têm rodinhas, o que lhe dá grande flexibilidade na hora de rearranjar seus armários (naturalmente, quando Mário troca dois armários de posição, ele também troca suas numerações, para que eles continuem numerados sequencialmente a partir de 1).
Para alugar armários para um novo cliente, Mário gosta de utilizar armários contíguos, pois no início da locação um novo cliente em geral faz muitas requisiç˜oes para acessar o conteúdo armazenado, e o fato de os armários estarem contíguos facilita o acesso para o cliente e para Mário.
Desde que Mário tenha armários livres em quantidade suficiente, ele sempre pode conseguir isso. Por exemplo, se a requisição de um novo cliente necessita de quatro armários, mas apenas os armários de número 1, 3, 5, 6, 8 estiverem disponíveis, Mário pode trocar os armários 5 e 2 e os armários 6 e 4 de posição: assim, ele pode alugar o intervalo de armários de 1 até 4.
No entanto, para minimizar o tempo de atendimento a um novo cliente, Mário quer fazer o menor número de trocas possível para armazenar cada volume. No exemplo acima, ele poderia simplesmente trocar os armários 1 e 4 de posição, e alugar o intervalo de 3 até 6.
Mário está muito ocupado com seus clientes e pediu que você fizesse um programa para determinar o número mínimo de trocas necessário para satisfazer o pedido de locação de um novo cliente.
Entrada
A primeira linha da entrada contém dois números inteiros N e L (1 ≤ N ≤ L ≤ 105 ), indicando quantos armários são necessários para acomodar o pedido de locação do novo cliente e quantos armários estão disponíveis, respectivamente. A segunda linha contém L inteiros distintos Xi (1 ≤ X1 < X2 < . . . < XL ≤ 109 ), em ordem crescente, indicando as posições dos armários disponíveis.
Saída
Seu programa deve produzir uma única linha, contendo um único número inteiro, indicando o número mínimo de trocas que Mário precisa efetuar para satifazer o pedido do novo cliente (ou seja, ter N armários consecutivos disponíveis).
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 6 |
0 |
|
5 5 |
2 |
|
5 6 |
1 |