Sinulla on n kolikkoa, joilla on tietyt arvot. Tehtäväsi on selvittää, mikä on pienin rahamäärä, jota ei voi muodostaa kolikoista.

Esimerkiksi jos kolikot ovat \{2,1,2,7\}, niistä voi muodostaa rahamäärät 1 \ldots 5 seuraavasti:

• 1 = 1
• 2 = 2
• 3 = 2+1
• 4 = 2+2
• 5 = 2+2+1

Kuitenkaan kolikoista ei voi muodostaa rahamäärää 6.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kolikoiden määrä.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: kolikoiden arvot. Usealla kolikolla voi olla sama arvo.

Tuloste

Tulosta pienin rahamäärä, jota ei voi muodostaa kolikoista.

Esimerkki 1

Syöte:

4
2 1 2 7

Tuloste:

6

Esimerkki 2

Syöte:

5
3 3 3 3 3

Tuloste:

1

Osatehtävä 1 (22 pistettä)

• 1 \le n \le 10
• 1 \le x_i \le 10

Osatehtävä 2 (35 pistettä)

• 1 \le n \le 100
• 1 \le x_i \le 1000

Osatehtävä 3 (43 pistettä)

• 1 \le n \le 10^5
• 1 \le x_i \le 10^9