28a Olimpíada Brasileira de Informática
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 |