Problema A - Palhotas
Infelizmente o mar vai levando a areia em muitas das praias
do nosso litoral e há cada vez menos espaço para a exploração
balnear. Por exemplo, na praia da sereia, já só se consegue plantar
uma fila de palhotas. Alguns clientes gostam de escolher a palhota
arbitrariamente, o que podem fazer se a palhota não estiver ocupada
por algum outro cliente que chegou mais cedo, mas outros, mais ciosos
da sua privacidade, preferem a palhota mais isolada, isto é, uma
palhota que esteja livre mas que esteja o mais afastada que for
possível de outras palhotas ocupadas. Claro que isto não garante nada,
pois logo a seguir pode vir outro cliente que escolhe a palhota logo
ao lado. Seja como for, o banheiro da praia da sereia instalou um
sofisticado serviço informático e pretende agora um programa para
apoiar os clientes na selecção da palhota mais isolada.
Os dados são o número de palhotas e os números das palhotas já
ocupadas. As palhotas são numeradas da direita para a esquerda, para
quem olha para o mar, começando em 1. O resultado é o número da
palhota mais isolada.
O Problema
Escreve um programa que, dado o número de palhotas e os números das
palhotas actualmente ocupadas, calcule qual a palhota livre mais isolada, isto é, mais longe de qualquer uma das outras.
Input
A primeira linha do input indica o número de palhotas,
N (1 <= N <= 100000). Em cada uma das linhas seguintes,
em número indeterminado mas maior ou igual a zero e menor ou igual a
N, vem um número inteiro entre 1 e N (inclusive), sem repetições,
representando uma palhota que está ocupada.
Output
O output contém apenas uma linha, na qual virá o número da
palhota mais isolada. Em caso de empate, prefere-se a palhota de
número mais baixo. Se a praia estiver cheia e não houver palhotas
livres, o programa escreve 0, convencionalmente.
Exemplo de Input 1
12
2
9
4
12
Exemplo de Output 1
6
Exemplo de Input 2
6
6
3
1
Exemplo de Output 2
2
Selecção dos Concorrentes Portugueses
Olimpíadas Internacionais de Informática 2007
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(3 de Agosto 2007)