Masala #C21BP09POF
Robotlar o'yini.
ravraS virtual o'yinlarni juda sevadi, va u ko'p vaqtlardan beri o'z o'yinini yaratish uchun harakat qilib yurgandi. Va yaratdi, o'yin sharti quyidagicha:
- Sizga \(n\) ta sondan iborat massiv beriladi. Massivdagi \(i(1≤i≤n)\)-element, \(i\)-robotning narxini bildiradi.
- Har qanday robot qo'shni robotga urush e'lon qilishi mumkin(qoshni robot-o'ngdagi yoki chapdagi eng yaqin robot, agarda o'ngda yoki chapda robot bo'lsa).
- Agar \(X\) narxga ega robot, \(Y\) narxga ega robotga urush e'lon qilsa, urush e'lon qilgan robot yutadi va uning narxi \(X-Y\) ga aylanadi, yutqazgan robot esa yo'q bo'lib ketadi.
O'yinda yutish uchun faqat bitta robot qolishi va narxi maksimal bo'lishi shart.
ravraSning ukasi sirakeB ham virtual o'yinlarni juda yaxshi koradi va u bunaqa oyinni oynamay qolishi mumkin emas edi.
Ammo u bu oyinda yutishga juda qiynaliyapti, va sizdan yordam soramoqda.
Birinchi qatorda \(n(1≤n≤10^6)\)-robotlar soni.
Ikkinchi qatorda \(n\) ta butun son \(aᵢ(-10^9≤aᵢ≤10^9)\), \(aᵢ\) - bu \(i\)-robotning narxi.
Bitta butun son - oxirgi robotning maksimal narxi.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 1 -2 |
3 |
| 2 |
3 -2 -1 1 |
4 |
| 3 |
4 2 2 -2 0 |
6 |
1-testta. 1-robot 2-robotga urush e'lon qiladi va o'yin tugaydi. Javob: 1-(-2)
2-testta. 2-robot 3-robotga urush e'lon qiladi. 2-robot narxi = -1-1 Robotlar narxi = [2,-2]. 1-robot 2-robotga urush e'lon qiladi. 1-robot narxi = 2-(-2). Robotlar narxi = [4]. O'yin tugaydi. Javob: 4.
Telegram kanalimizga obuna bo'ling