← К соревнованиям

Sort Me Round

Бредовая система счисления

Сложность: 32%

В попытках впечатлить учителя информатики Лиза придумала собственную систему счисления. В этой системе есть nn разрядов, каждый из который может быть установлен в состояние 0 или 1. Алгоритм перевода из Лизиной системы в десятичную прост: пробежимся по всем разрядам с конца, и для каждого ii-го разряда со значением 1 добавим к ответу натуральное число aia_i.

Учитель назвал Лизину систему “Бредовой”, потому что в ней якобы можно записать лишь небольшое множество чисел. Лиза очень расстроилась, упала к вам в объятия в слезах и, всхлипывая, рассказала эту историю. Нежно вытирая слёзы с её румяных щёк, вы успокоили Лизу и объяснили, что её система - самая лучшая!

На утро вы аккуратно, не будя Лизу, пошли к компьютеру и решили всё-таки проверить, насколько её учитель прав. Найдите самый маленький натуральный xx, который нельзя записать в Лизиной системе.

Входные данные

В первой строке записано натуральное число nn (1n21051 \le n \le 2 \cdot 10^5) – количество разрядов в Лизиной системе.

В следующей строке записаны числа a1a_1, a2a_2 ... ana_n (1ai1091 \le a_i \le 10^9).

Выходные данные

Выведите одно число xx – самое маленькое натуральное число, которое нельзя записать в Лизиной системе счисления.

Подзадачи

баллынеобх. подзадачиограничения
1

20

-

n10n \le 10

2

50

1

n1500n \le 1500

3

30

2

Нет доп. ограничений

STDINSTDOUT
5
1 2 9 1 3
8