CSES - Soittolista
  • Time limit: 2.00 s
  • Memory limit: 128 MB

Uolevi on laatinut itselleen soittolistan, joka muodostuu peräkkäin soitettavista kappaleista.

Uolevi kuuntelee musiikkia vain matkustaessaan bussissa. Kun hän astuu sisään bussiin, hän valitsee jonkin kohdan soittolistasta ja alkaa kuunnella musiikkia siitä eteenpäin. Jos listan viimeinen kappale päättyy eikä bussi ole vielä perillä, Uolevi suuttuu. Samoin käy, jos kappale jää kesken bussin saapuessa perille.

Joskus Uolevi myös päivittää soittolistaa, jolloin hän vaihtaa tietyssä kohdassa olevan kappaleen toiseksi.

Tehtäväsi on selvittää, montako kertaa Uolevi suuttuu tapahtumien aikana.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: soittolistan kappaleiden määrä. Kappaleet on numeroitu kokonaisluvuin 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua s_1,s_2,\ldots,s_n: soittolistan kappaleiden kestot.

Sitten syötteessä on kokonaisluku q: tapahtumien määrä.

Lopuksi syötteessä on q riviä, joista jokainen kuvaa yhden tapahtuman. Jokaisella rivillä on kolme kokonaislukua t, k ja x. Jos t=1, Uolevi alkaa kuunnella listaa kappaleesta k ja bussimatka kestää x minuuttia. Jos t=2, Uolevi vaihtaa listaan kohtaan k kappaleen, jonka kesto on x minuuttia.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: kuinka monta kertaa Uolevi suuttuu tapahtumien aikana.

Rajat

  • 1 \le n \le 10^5
  • 1 \le s_k \le 10^9
  • 1 \le q \le 10^5
  • 1 \le t \le 2
  • 1 \le k \le n
  • 1 \le x \le 10^9

Esimerkki

Syöte:

5
3 1 1 2 1
5
1 4 1
1 4 3
1 4 5
2 5 7
1 4 3

Tuloste:

3