Piramida axtarışı
"Фуфелшмертц Pakost İnkorporated" yenə də pislik edir! İndi o, hər gün Yer kürəsinin litosfer plitələrini hərəkət etdirir. Peri-ördəksu vacib bir tapşırıq aldı: hər gün birbaşa xətt üzərində ən şübhəli relyefi axtarmaq və sonra, əlbəttə ki, bu barədə agentliyə məlumat vermək.
Onun nəzarətində bir düz xətt üzərində yerləşən n sahə var. Hər bir sahə bir ədəd h[i] - dəniz səviyyəsindən yuxarı olan hündürlüyü ilə xarakterizə olunur. Bir sıra şübhəli adlanır, əgər orada elə bir sahə varsa ki, onun solundakı sahələrin hündürlükləri ciddi şəkildə artır, sağındakı isə ciddi şəkildə azalır. Bununla belə, Fufelşmerts'in hiylələri səbəbindən sahələrin hündürlükləri daim dəyişir.
Periyə hər dəyişiklikdən sonra ən uzun şübhəli sahə sırasının uzunluğunu müəyyən etməyə kömək edin. Hər an iki yanaşı sahənin eyni hündürlükdə olmadığına zəmanət verilir.
Giriş məlumatları
Birinci sətirdə bir ədəd n (1 ≤ n ≤ 10^5) - sahələrin sayı verilir. İkinci sətirdə n ədəd - sahələrin hündürlükləri (|h[i]| ≤ 10^18) verilir.
Üçüncü sətirdə m (1 ≤ m ≤ 10^5) - dəyişikliklərin sayı verilir. Növbəti m sətirdə iki tam ədəd x və y (1 ≤ x ≤ n, |y| ≤ 10^18) - hündürlüyü dəyişən sahənin indeksi və həmin sahənin yeni hündürlüyü verilir.
Çıxış məlumatları
m ədəd çıxarın, i-ci ədəd i-ci dəyişiklikdən sonra ən uzun şübhəli sahə sırasının uzunluğuna bərabərdir.