CSES - Summat
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinulla on taulukko, jossa on nn lukua. Taulukon sisältöön tulee muutoksia, ja tehtäväsi on ilmoittaa joka muutoksen jälkeen suurin yhtenäisen välin summa taulukossa.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvut nn ja mm: taulukon koko ja muutosten määrä. Taulukon kohdat on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden muutoksen. Rivillä on kaksi kokonaislukua kk ja xx: kohtaan kk tulee luku xx.

Tuloste

Ohjelmasi tulee tulostaa jokaisen muutoksen jälkeen suurin yhtenäisen välin summa taulukossa.

On sallittua, että väli on tyhjä, jolloin sen summa on 0.

Rajat

  • 1n,m1051 \le n, m \le 10^5
  • 109xi109-10^9 \le x_i \le 10^9
  • 1kn1 \le k \le n
  • 109x109-10^9 \le x \le 10^9

Esimerkki

Syöte:

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

Tuloste:

9
13
6