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 nn: soittolistan kappaleiden määrä. Kappaleet on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua s1,s2,,sns_1,s_2,\ldots,s_n: soittolistan kappaleiden kestot.

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

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

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1sk1091 \le s_k \le 10^9
  • 1q1051 \le q \le 10^5
  • 1t21 \le t \le 2
  • 1kn1 \le k \le n
  • 1x1091 \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