URI Online Judge | 2452

Semente

Por OBI - Olimpíada Brasileira de Informática 2014 BR Brazil

Timelimit: 1

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.

Você foi contratado para escrever um programa que, dados o comprimento da fita de papel e as posições das gotas de reagente no início do experimento, determine quantos dias serão necessários para a fita de papel ficar completamente tomada pelo reagente.

Entrada

A primeira linha contém dois inteiros F (1 ≤ F ≤ 100000) e R (1 ≤ R ≤ 1000), 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.

Exemplos de Entrada Exemplos de Saída

13 3 
2 6 13 

3

10 2 
9 10 

8