Kazak Vus və Möcüzələr Tarlası#10361
Kozak Vus, Möcüzələr Sahəsi adlanan və pul ağaclarının yetişdiyi maraqlı bir yer haqqında məlumat aldı. O, pul ağacı əkməyə və gələn il məhsul yığmağa qərar verdi.
Kozak Vus Möcüzələr Sahəsinə qayıdanda, hər ağacda ən azı bir sikkə yetişdiyini və -ci ağacda sikkələrin sayının a_i olduğunu öyrəndi. Məhsulu təkbaşına yığmağın çox uzun çəkəcəyini düşündüyü üçün, aşağıdakı əməliyyatı yerinə yetirə bilən bir maşın hazırladı:
Müəyyən bir müsbət ədədini seçmək;
Hal-hazırda ən azı sikkəsi olan ilk ağacı (ən kiçik indeksli ağacı) tapmaq;
Ondan sikkə götürmək.
Lakin pul ağaclarına qulluq kitabçasında Kozak Vus öyrəndi ki, məhsul yığdıqdan sonra hər ağacda ən azı bir sikkə qalmalıdır, əks halda onlar gələn il məhsul verməyəcəklər.
İndi Kozak Vus maraqlanır ki, müəyyən sayda əməliyyatdan sonra maşın maksimum nə qədər məhsul yığa bilər.
Qeyd edək ki, ədədi müxtəlif əməliyyatlar üçün fərqli ola bilər.
Birinci sətir Möcüzələr Sahəsindəki ağacların sayını göstərən bir tam ədəd (1 \leq n \leq 10^6) ehtiva edir.
İkinci sətir ağaclarda başlanğıcda olan sikkələrin sayını göstərən tam ədədi a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) ehtiva edir.
Tək bir tam ədəd çıxarın - hər ağacda ən azı bir sikkə qalmaq şərti ilə maşının müəyyən bir əməliyyat ardıcıllığından sonra yığa biləcəyi maksimum sikkə sayı.
Nümunə 1
Nümunə 2
İkinci nümunədə hər ağacda sikkələr qalmaq şərti ilə heç olmasa bir sikkə yığmaq üçün elə bir seçmək mümkün deyil.
( bal): n=2;
( bal): n=3;
( bal): a_i \leq 2;
( bal): a_i \leq 3;
( bal): 10 \leq a_i;
( bal): a_i, n \leq 1\,000;
( bal): əlavə məhdudiyyətlərsiz.