Арсен — ержүрек қазына іздеуші, ол жақында \(n\) сиқырлы кристалдар жатқан құпия қазына сандығын тапты. Әр кристалдың бүтін санмен берілетін қуаты бар. Дегенмен, бұл кристалдарды сол күйінде қалдыруға болмайды — олардың саны көбейген сайын, олардан шығатын ерекше сәуле күшейеді.

Өзінің қауіпсіздігін қамтамасыз ету үшін Арсен тек бір кристалды қалдыруды шешті, бірақ мұны ақылмен жасағысы келеді. Ол кристалдармен келесі әрекеттерді орындауға мүмкіндік беретін көне ритуалды тапты:

Сандықтағы бір кристалды (индексі \(i\)) таңдайды. Осы кристалдың күшін пайдаланып қалғандарын әлсіретеді. Бұл дегеніміз, қалған барлық кристалдар үшін (\(j \neq i\)), олардың күші таңдалған кристалдың күшіне азаяды: \(a_j = a_j - a_i\). Ритуалды орындағаннан кейін таңдалған кристал жоғалады. Әр ритуалды орындаған сайын, сандықтағы кристалдардың саны біреуге азаяды. \(n-1\) ритуал орындалғаннан кейін сандықта тек бір кристал қалады.

Арсен соңғы қалған кристалдың ең қуатты болғанын қалайды. Оған барлық ритуалдарды орындағаннан кейін қалған кристалдың максималды мүмкін күшін табуға көмектесіңіз!

Енгізу

Бірінші жолда \(n\) \((1 \le n \le 10^5)\) бүтін саны — кристалдардың саны беріледі.

Екінші жолда \(n\) бүтін саны — \(a_1, a_2, ..., a_n\) \((-10^9 \le a_i \le 10^9)\), әр кристалдың күші беріледі.

Шығару

Барлық ритуалдар орындалғаннан кейін қалған кристалдың максималды мүмкін күшін шығарыңыз.

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

Мысалдар

Енгізу 1

3
3 7 5

Жауап 1

4