Süni göl#10154

Süni göl

1 saniyə

128 meqabayt

Çətin

İsti yay günləri inəklərin narazılığını misli görünməmiş səviyyəyə çatdırıb. Fermer Con nəhayət süni göl tikməyə qərar verib. Öz mühəndislik araşdırmaları çərçivəsində o, gölü tezliklə su altında qalacaq $n$ qonşu səviyyədən ibarət ardıcıllıqdan təşkil olunmuş ikiölçülü relyef kimi modelləşdirir. Səviyyələr soldan sağa $1 \dots n$ ilə nömrələnib.

Hər $i$ səviyyəsi iki tam ədədlə təsvir olunur: onun eni $w_{i} (1 \leq w_{i} \leq 1000)$ w_i~(1 \le w_i \le 1000) və hündürlüyü (onun nisbi hündürlük nişanını göstərən) $h_{i} (1 \leq h_{i} \leq 1 0^{6})$ h_i~(1 \le h_i \le 10^6). Bütün səviyyələrin hündürlükləri fərqlidir. Gölün modeli soldan və sağdan sonsuz hündürlüyə malik divarlarla məhdudlaşdırılır. Gölün profilinin nümunəsi aşağıda göstərilib.

         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- hündürlük
         *    **********  3
         ***************  2
         ***************  1
Səviyyə  |  1 |2|  3   |

Fermer Conun modelində gölün doldurulması gündoğandan başlayır. Su ən aşağı nöqtəyə dəqiqədə $1$ kvadrat vahid su sürəti ilə daxil olur. Su üfüqi səthlə qarşılaşana qədər şaquli aşağı düşür, bundan sonra isə adi suda olduğu kimi axır və yayılır. Hər bir yaxşı riyazi modeldə olduğu kimi, suyun düşməsi və axmasının ani baş verdiyini qəbul edəcəyik.

Hər bir səviyyənin $1$ hündürlüyündə su təbəqəsi ilə örtüldüyü an vaxtı təyin edin.


SU                    SU DAŞIR
       |                       |
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     4 dəqiqədən sonra   26 dəqiqədən sonra   50 dəqiqədən sonra
     Səviyyə 1 batıb     Səviyyə 3 batıb      Səviyyə 2 batıb

Xəbərdarlıq: Cavab həmişə $32$ -bitlik tam ədəd tipinə sığmaya bilər.

Giriş

Birinci sətirdə bir tam ədəd $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) verilir.

Sonrakı $n$ sətirdən hər birində $i (1 \leq i \leq n)$ i~(1 \le i \le n) səviyyəsinin təsviri — iki tam ədəd $w_{i}$ w_i və $h_{i}$ h_i verilir.

Çıxış

$n$ sətir çap edin. $i (1 \leq i \leq n)$ i~(1 \le i \le n)-ci sətirdə bir tam ədəd — gündoğandan sonra neçə dəqiqə ərzində $i$ səviyyəsinin $1$ hündürlüyündə su təbəqəsi ilə örtüldüyünü çap edin.

Nümunələr

Nümunə 1