Faites place ! – Qualification 2018

Level 2

Énoncé

Aujourd'hui, Joseph Marchand a décidé de vendre des crêpes lui aussi. Malheureusement, il est arrivé un peu tard : tous les autres marchands ont déjà positionné leur stand, et Joseph doit se faire une place parmi eux, en choisissant une des positions restantes.

On considère encore la plage comme un segment de la position 0 (le plus à l'ouest), à la position $N$ (le plus à l'est de la plage).

Les clients vont toujours acheter leurs crêpes auprès du marchand le plus proche d'eux, sans regarder les différences de prix ou de garnitures (c'est les vacances après tout, le moindre effort est épuisant). Joseph Marchand veut se placer afin d'avoir la plus grande zone d'influence possible sur les clients. Il doit se placer sur une position entière où un marchand n'est pas déjà installé. On rappelle que la zone d'influence d'un marchand est l'ensemble des points (pas forcément entiers) de la plage dont il est plus proche que n'importe quel autre marchand.

Joseph cherche à savoir quelle serait la taille de la plus grande zone d'influence qu'il peut avoir, arrondie à l'entier inférieur.

Entrée

L'entrée contiendra trois lignes. La première donnera la longueur $N$ de la plage (considérée comme une ligne droite), la deuxième le nombre $M$ de marchands déjà arrivés sur place, et la troisième listera les emplacements $E_i$ de ces marchands (numéros croissants compris entre $0$ et $N$).

Sortie

Vous afficherez un entier, la taille de la zone d'influence maximale que peut avoir Joseph.

Contraintes

  • $1 \le N \le 1\ 000\ 000$
  • $1 \le M \le 10\ 000$
  • $1 \le E_i \le N$

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
1
3
Sample output
6
Note

Sample input
50
2
10 40
Sample output
15
Note

Submit your solution

You have to register or log in to be able to submit your solution.