Калашников "X" кітаптар сериясын оқуға дайындалып жатыр, ол \(10^9\) томнан тұрады. Бастапқыда оның осы сериядан \(N\) томы бар. \(i\)-ші томның нөмірі \(a_i\).

Оқу басталғанға дейін ол кез келген рет (мүмкін 0 рет) келесі әрекетті орындай алады: - Егер оның \(1\) немесе одан аз кітабы болса, ол ештеңе жасамайды. - Әйтпесе, ол екі кітапты сатып, кез келген бір томды сатып алады.

Осыдан кейін Калашников кітаптарды оқи бастайды, \(1\)-томнан бастап ретімен \((2, 3, 4, \dots)\) жалғастырады. Егер оған қажетті келесі том жетіспесе, ол тоқтайды және ары қарай оқи алмайды.

Оның оқи алатын ең үлкен томының нөмірін табыңыз. Егер ол ештеңе оқи алмаса, \(0\) шығарыңыз.

Енгізу

Бірінші жолда бір бүтін сан \(N\) — қолдағы кітаптар саны \((1 \leq N \leq 3 \times 10^5)\). Екінші жолда \(N\) бүтін сандар \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq 10^9)\) — бар томдардың нөмірлері.

Шығару

Бір бүтін санды шығарыңыз — Калашников оқи алатын ең үлкен том. Егер ол ешбір кітапты оқи алмаса, \(0\) шығарыңыз.

Бағалау жүйесі

• \(N \leq 3000\) болатын 20 тест, әрқайсысы 2 ұпайдан бағаланады.

• \(N \leq 300000\) болатын 20 тест, әрқайсысы 3 ұпайдан бағаланады.

Мысалдар ұпайға әсер етпейді.

Мысалдар

Енгізу 1

6
1 2 4 6 7 100

Жауап 1

4