Premier absent

Ce matin, en arrivant en cours, vous êtes le seul à l'heure : tous vos camarades sont en retard ou absents. Comme d'habitude, après un certain temps, votre professeur va faire l'appel dans l'ordre alphabétique, et va punir très sévèrement le premier élève qui ne répondra pas présent. Il sera plus clément pour les suivants car il aura déjà réussi à déverser sa rage quotidienne sur quelqu'un.

Les autres élèves arrivent un par un, dans un ordre quelconque. À chaque fois que l'un d'eux arrive, vous vous demandez quel serait l'élève puni, si votre professeur faisait l'appel juste après l'arrivée du nouvel élève.

Les élèves sont numérotés en fonction de leur position dans l'ordre d'appel. Étant donnée la liste des élèves qui arrivent, votre programme doit calculer, pour chaque nouvel élément de la liste, l'élève ayant l'identifiant le plus petit qui n'est pas présent à ce moment.

• 1 ≤ N ≤ 1 000 000 000, où N est le nombre d'élèves inscrits dans votre classe.
• 1 ≤ P ≤ 250 000, où P est le nombre d'élèves présents aujourd'hui.
• 1 ≤ E_i ≤ N, où E_i est l'identifiant d'un élève.

• Dans 20% des fichiers tests, on a N ≤ 1 000 et P ≤ 1 000.
• Dans 70% des fichiers tests, on a N ≤ 250 000.

• La première ligne de l'entrée contient deux entiers séparés par un espace : N et P.
• Les P lignes suivantes contiennent chacune un entier : l'identifiant d'un élève qui arrive en cours, c'est-à-dire sa position dans la liste alphabétique des élèves de la classe. On vous garantit que chaque identifiant n'apparaît qu'une fois.

Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Si tous les élèves inscrits sont présents, vous devez afficher -1.

Lorsque le premier élève (vous, avec l'identifiant 4) arrive, l'élève 1 est l'élève absent ayant l'identifiant le plus faible. À l'étape suivante, cet élève arrive et l'identifiant de l'élève absent qui suit est 2, jusqu'à ce qu'il arrive à la dernière étape. À la fin, l'élève 5 est l'élève absent le premier dans l'ordre d'appel.

Indications C++ pour lire et afficher des entiers :

   #include <cstdio>
   int main() {
      ... 
      scanf("%d", &valeur);   // pour lire
      printf("%d\n", valeur); // pour écrire
      ...
   }

Indications Caml pour lire et afficher des entiers

   let scan_int () = Scanf.scanf " %d" (fun x -> x)  
   let show_int n = Printf.printf "%d\n" n           
   let _ = ... votre code ...
   (* pour lire, faire "let valeur = scan_int() in .." *)
   (* pour écrire, faire "show_int valeur; .." *)