Məşhur Şəhər

Mr. B Varşavaya gəldikdən sonra göydələnlərin çoxluğundan heyrətə gəldi və bir neçə şəkil çəkdi. Lakin indi bu şəkillərə baxarkən, oradakı binaların sayını belə müəyyən edə bilmir. Buna görə də, o, problemi aşağıdakı şəkildə həll etməyə qərar verdi:

• Şəkli soldan sağa doğru n şaquli hissəyə bölün. Şəkildəki binalar üfüq xətti olan düzbucaqlılar kimi qəbul edilə bilər. Bir bina bir neçə ardıcıl hissəni əhatə edə bilər, lakin hər bir hissə yalnız bir görünən bina və ya heç bir bina ehtiva edə bilməz.

• Hər bir hissədəki binanın hündürlüyünü ölçün.

• Fotodakı minimum bina sayını hesablamaq üçün bir proqram yazın.

Mr. B ilk iki addımı tamamladı, sonuncusu isə sizin vəzifənizdir.

Giriş verilənləri

Hər bir test halı bir tam ədəd n (1 ≤ n ≤ 100000) olan bir sətirlə başlayır. Bunun ardınca, hər bir hissədəki binanın hündürlüyünü göstərən n tam ədəd gəlir. Qeyd edək ki, sıfır hündürlük o hissədə ümumiyyətlə bina olmadığını göstərir. Bütün daxil edilən ədədlər qeyri-mənfi və 1000000000-dən kiçik olacaq.

Çıxış verilənləri

Hər bir test halı üçün, hal nömrəsini və fotodakı mümkün minimum bina sayını göstərən bir sətir çıxarın.

Nümunələr

Qeyd

Nümunələrin mümkün konfiqurasiyaları aşağıda göstərilmişdir: