28a Olimpíada Brasileira de Informática
Submeta sua solução

Dígitos

Joãozinho te propôs o seguinte desafio: ele escolheu dois inteiros A e B, com 1 ≤ A ≤ B ≤ 10^{1000}, e escreveu na lousa todos os inteiros entre A e B, em sequência, porém colocando um espaço após cada dígito, de forma a não ser possível ver quando um número termina ou começa. Por exemplo, se Joãozinho escolher A = 98 e B = 102, ele escreveria a sequência "9 8 9 9 1 0 0 1 0 1 1 0 2". Seu desafio é: dada a lista de dígitos escritos na lousa, encontrar os valores de A e B. Caso exista mais de uma possibilidade para os valores que geraria a lista, você deve encontrar uma em que o valor de A é o menor possível. É garantido que a lista de dígitos da lousa tem no máximo tamanho 1000.

Entrada

A primeira linha da entrada contém um único inteiro N, indicando o número de dígitos. A segunda linha contém N inteiros di, indicando os dígitos escritos.

Saída

Imprima o menor valor possível de A.

Restrições

  • 1 ≤ N ≤ 1000
  • 0 ≤ di ≤ 9

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 21 pontos, 1000 ≤ A ≤ B ≤ 9999.
  • Para outro conjunto de casos de testes valendo 23 pontos, B = A + 1.
  • Para outro conjunto de casos de testes valendo 40 pontos, A,B < 10^{6}.
  • Para outro conjunto de casos de testes valendo 16 pontos, nenhuma restrição adicional.

Exemplos

Entrada
6
1 2 3 1 2 4
Saída
123
	

 

Entrada
6
8 9 1 0 1 1
Saída
8
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação