Арсеннің қазынасы
Арсен — ержүрек қазына іздеуші, ол жақында \(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\) | \(n = 2\) | \(10\) | — |
| \(2\) | \(n \le 8\) | \(15\) | 1 |
| \(3\) | \(n \le 2000\) | \(25\) | \(1\), \(2\) |
| \(4\) | — | \(50\) | \(1\), \(2\), \(3\) |
Мысалдар
Енгізу 1
3
3 7 5Жауап 1
4
Пікірлер
Объяснение первого примера задачи Сокровища Арсена. Сначала отнимает третий кристал, получается -2 2 0. Затем отнимаем первый кристал, получается 0 4 0. Вот так выходит 4
Бірінші мысалдың түсіндірмесі. Алдымен үшінші кристалды алып тастаймыз, нәтижесінде -2 2 0 болады. Содан кейін бірінші кристалды алып тастаймыз, нәтижесінде 0 4 0 болады. Міне, осылайша 4 шығады.
First, subtract the third crystal, resulting in -2 2 0. Then subtract the first crystal, resulting in 0 4 0. That's how it turns out to be 4.