XXVI Olimpíada Brasileira de Informática
Semente
Um experimento biológico utiliza uma fita de papel branco especial, na qual algumas gotas de um reagente são colocadas em posições específicas. Inicialmente a gota de reagente faz com que o papel se torne preto na posição em que foi colocada. A cada dia o reagente se propaga pelo papel, em todas as direções, com velocidade de 1 posição por dia, colorindo a região em que o reagente se propagou. A figura abaixo mostra um experimento com uma fita de 13 posições, com três gotas de reagente inicialmente, colocadas nas posições 2, 6 e 13 (a posição 1 é a primeira mais à esquerda da fita). Ao final do terceiro dia, a fita está completamente tomada pelo reagente.
Entrada
A primeira linha contém dois inteiros F e R, indicando respectivamente o comprimento da fita de papel, em números de posições, e o número de gotas no início do experimento. A segunda linha contém R inteiros, indicando as posições das gotas de reagente, que são dadas em ordem crescente.Saída
Seu programa deve produzir uma única linha, contendo um único inteiro, o número de dias necessários para que a fita de papel fique totalmente tomada pelo reagente.Restrições
- 1 ≤ F ≤ 100000, 1 ≤ R ≤ 1000
Informações sobre a pontuação
- Em um conjunto de casos de teste equivalente a 80 pontos, F ≤ 1000.
Exemplos
Entrada
13 3 2 6 13 |
Saída
3 |
Entrada
10 2 9 10 |
Saída
8 |
