Yetishmayotgan summa

Sizda $n$ ta tanga bor, har birining qiymati musbat butun son. Har bir tangani ko'pi bilan bir marta ishlatib, hosil qilib bo'lmaydigan eng kichik musbat summani toping.

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($1 \le a_i \le 10^9$).

Bitta son — hosil qilib bo'lmaydigan eng kichik musbat summa.

Tangalarni o'sish tartibida saralang. Faraz qiling, birinchi $k$ ta tanga bilan $1$ dan $s$ gacha barcha summalarni hosil qilish mumkin. Keyingi tanga $a \le s + 1$ bo'lsa, endi $1$ dan $s + a$ gacha hammasi hosil bo'ladi. $a > s + 1$ bo'lsa, $s + 1$ ni hech qachon hosil qilib bo'lmaydi — u javob.

Birinchi misolda saralangan tangalar $1, 2, 2, 7$: $s = 5$, keyingi tanga $7 > 6$ — javob $6$. Javob $2 \cdot 10^{14}$ gacha yetadi — 64 bitli tur kerak.

Manba: CSES, 2183-masala, acmp.ru, 427-masala.