Lift problemi#8330
Zirzəmi (sıfırıncı) mərtəbəsində böyük universitet binasının tələbələri lift gözləyirlər. Adətən lift hər mərtəbədə dayanır və burada bir və ya bir neçə tələbə çıxmalıdır. Bu, daha yuxarıda çıxmaq istəyənləri narahat edir. Digər tərəfdən, lift bəzi mərtəbələri keçə bilər ki, bu da həmin mərtəbədə çıxmaq istəyən tələbələri narahat edir.
Xüsusilə, tələbə lift öz mərtəbəsinə çatana qədər liftin dayandığı hər mərtəbədə narahat olur. Əgər lift tələbənin çıxmaq istədiyi mərtəbəni keçirsə, tələbə həmin mərtəbədə və lift növbəti dəfə dayanana qədər yuxarıdakı hər mərtəbədə narahat olur (bu mərtəbədə tələbə artıq narahat olmur), sonra tələbə çıxır və pilləkənlərlə təyinat yerinə enməyə başlayır.
Məsələn, əgər tələbə beşinci mərtəbədə çıxmaq istəyirsə, amma lift ikinci, yeddinci və onuncu mərtəbədə dayanırsa, tələbə ikinci, beşinci və altıncı mərtəbələrdə narahat olacaq. Ümumilikdə bu tələbə üç mərtəbədə narahat olacaq.
Liftə daxil olan hər tələbə, hətta düymə artıq başqası tərəfindən basılmış olsa belə, öz mərtəbəsinə uyğun düyməni basır. Beləliklə, liftə nəzarət edən mərkəzi prosessor hər mərtəbədə neçə tələbənin çıxmaq istədiyini dəqiq bilir.
Sizdən Mərkəzi Prosessoru proqramlaşdırmaq tələb olunur ki, hansı mərtəbələrdə dayanmaq lazım olduğunu həll etsin. Məqsəd ümumi narazılıq səviyyəsini minimuma endirməkdir: hər tələbənin narahat olduğu mərtəbələrin sayı bütün tələbələr üçün cəmlənir.
Siz yuxarı mərtəbədə liftə minmək istəyən bütün insanları nəzərə almaya bilərsiniz. Lift elə işləməlidir ki, zirzəmi mərtəbəsində onu gözləyən hər tələbə ya öz mərtəbəsində, ya da müəyyən bir mərtəbədə çıxıb pilləkənlərlə aşağı enə bilsin.
Birinci sətir testlərin sayını ehtiva edir, 100-dən çox deyil. Daha sonra hər test üçün:
birinci sətir n (1 ≤ n ≤ 1500) - zirzəmi mərtəbəsi istisna olmaqla binadakı mərtəbələrin sayını ehtiva edir.
bir sətir n tam ədədi s[i] (0 ≤ s[i] ≤ 1500) ehtiva edir: s[i] i-ci mərtəbədə çıxmaq istəyən tələbələrin sayına bərabərdir.
Hər test üçün ayrı sətirdə liftin ümumi narazılıq səviyyəsinin mümkün olan ən kiçik dəyərini çıxarın.
Nümunə 1