Kazak Vus və Möcüzələr Tarlası

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, $n$ 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ə $i$-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 $k$ ədədini seçmək;

• Hal-hazırda ən azı $k$ sikkəsi olan ilk ağacı (ən kiçik indeksli ağacı) tapmaq;

• Ondan $k$ 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, $k$ ədədi müxtəlif əməliyyatlar üçün fərqli ola bilər.

Giriş verilənləri

Birinci sətir Möcüzələr Sahəsindəki ağacların sayını göstərən bir tam ədəd $n$ ($1\le n\le 10^6$) ehtiva edir.

İkinci sətir ağaclarda başlanğıcda olan sikkələrin sayını göstərən $n$ tam ədədi $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) ehtiva edir.

Çıxış verilənləri

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ələr

Qeyd

İkinci nümunədə hər ağacda sikkələr qalmaq şərti ilə heç olmasa bir sikkə yığmaq üçün elə bir $k$ seçmək mümkün deyil.

Qiymətləndirmə

1. ($4$ bal): $n=2$;

2. ($8$ bal): $n=3$;

3. ($7$ bal): $a_i\le 2$;

4. ($13$ bal): $a_i\le 3$;

5. ($7$ bal): $10\le a_i$;

6. ($19$ bal): $a_i,n\le 1000$;

7. ($42$ bal): əlavə məhdudiyyətlərsiz.