Neznaykanın və dostlarının macəraları

Hamımız Neznaykanın dostları ilə birlikdə hava şarı ilə səyahətə çıxdığı hekayəni xatırlayırıq. Lakin hər kəs bilmir ki, hava şarının yükqaldırma qabiliyyəti məhdud olduğu üçün bütün adamlar ora yerləşə bilmədi.

Bu məsələdə sizdən tələb olunur ki, neçə nəfərin səyahətə çıxdığını öyrənəsiniz. Məlumdur ki, şara minmə optimal deyil, yəni adamlar sırada durduqları qaydada şara minirlər, onlardan birinə yer çatmadıqda, o və sırada qalan bütün adamlar geri dönüb evlərinə gedirlər.

Giriş verilənləri

Birinci sətirdə çiçək şəhərindəki adamların sayı $n(1\le n\le 10^6)$ verilir. İkinci sətirdə onların şara minmə sırasına uyğun çəkiləri verilir. Bütün çəkilər natural ədədlərdir və $10^9$-u keçmir. Daha sonra sorğuların sayı $m(1\le m\le 10^5)$ verilir. Hər bir sorğu bir sətirdən ibarətdir. Sətirdəki ilk ədəd $t$ sorğunun tipini göstərir.

• Əgər $t=1$-dirsə, onda daha bir ədəd $v(1\le v\le 10^9)$ verilir — hava şarının yükqaldırma qabiliyyəti.

• Əgər $t=2$-dirsə, onda iki ədəd $x(1\le x\le n)$ və $y(1\le y\le 10^9)$ verilir — $x$ mövqeyindəki adamın çəkisi $y$ olur.

Çıxış verilənləri

Birinci tipli hər bir sorğu üçün ayrıca sətirdə şara yerləşən adamların sayını yazın.

Nümunələr