Masala #0185

Xotira 64 MB Vaqt 1000 ms
14

Biznesmen Jinni

Bir jinni uy oldi sottisi bilan shug’ullanar ekan. Uning jinniligi shunda ekanki, u hech qachon sotib olgan uyini xarid narxidan qimmatga sotmas ekan, ya’ni u bu savdodan hech qanday foyda ko’rmaydi, bunga sabab uning boshqa bizneslari mavjudligi va bu kasbni shunchaki hobbiy sifatida qabul qilishida. Unda hozirda bir uyning N kun davomidagi narxlarining o’zgarish grafigi bor, shu N kun ichida uyni xarid qilishi va uni xarid narxidan ko’p bo’lmagan pulga sotishi kerak(xarid qilingan kundan keying kunlardagina sotish mumkin).


Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida bitta butun son, N(1 ≤ N ≤ 200000). Keyingi qatorda N ta [1, 1016] oralig’idagi butun son, uy narxining grafigi berilgan.


Chiquvchi ma'lumotlar:

Biznesmen Jinnining eng kam ziyoni qancha bo’lishini aniqlang. Yechim mavjudligi kafolotlanadi.


Misollar
# input.txt output.txt
1
3
5 10 3
2
2
5
20 7 8 2 5
2