Suncokret

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 512M
Problem type
Allowed languages
Assembly, Awk, C, C++, Java, Perl, Python

Ivica je strastveni ljubitelj bilja. U vrtu ima razne vrste cvijeća, no najdraži su mu suncokreti. Pred njegovom kućom nalazi se \(N\) suncokreta poredanih uz ogradu slijeva nadesno. Početna visina \(i\)-tog suncokreta je \(A_i\) centimetara. Da bi neki suncokret narastao za \(X\) centimetara potrebno ga je zaliti s \(X\) litara vode.

Ivica bi želio da njegovi suncokreti budu takvi da im visine budu neopadajuće slijeva nadesno, tj. da nijedan suncokret ne bude niži od nekog koji se nalazi lijevo od njega.

Ivičin susjed Krešo voli potajno zalijevati suncokrete pa je u \(i\)-toj od \(Q\) narednih noći odlučio \(X_i\)-ti suncokret zaliti s \(Y_i\) litara vode.

U svakom od tih \(Q\) dana Ivica se probudio i vidio da se visina nekog suncokreta povećala. Bez namjere da to stvarno učini, zapitao se koliko bi mu minimalno litara vode trebalo da visine suncokreta tog dana pretvori u neopadajuće slijeva nadesno.

Kako se Ivica treba brinuti i o ostalim biljkama, moli tebe da mu pomogneš odrediti odgovore na postavljena pitanja.

Ulazni​ podaci

U prvom retku nalaze se prirodni brojevi \(N\) i \(Q\) \((1 \leq N, Q \leq 100 000)\), brojevi iz teksta zadatka.

U drugom retku nalazi se niz \(A\) od \(N\) prirodnih brojeva \(( 1 \leq A_i \leq 10^9 )\), brojevi iz teksta zadatka.

U sljedećih \(Q\) redaka nalaze se po dva prirodna broja \(X_i\) i \(Y_i\) \((1 \leq X_i \leq N, 1 \leq Y_i \leq 10^9 )\), brojevi iz teksta zadatka.

Izlazni podaci

U svakom od \(Q\) redaka ispišite po jedan cijeli broj, redom odgovore na pitanja iz teksta zadatka.

Bodovanje

U test podacima ukupno vrijednima \(30\) bodova vrijedit će \(1 \leq N, Q \leq 1000\).

Primjeri test​ podataka

Ulaz
5 4
1 3 2 2 4
1 2
2 3
4 5
1 1
Izlaz
2
10
7
7
Objašnjenje
i Visine suncokreta u \(i\)-tom danu Visine u \(i\)-tom danu kad bi Ivica zalio suncokrete na optimalan način Odgovor na \(i\)-to pitanje
\(1\) \(3, 3, 2, 2, 4\) \(3, 3, 3, 3, 4\) \(0 + 0 + 1 + 1 + 0 = 2\)
\(2\) \(3, 6, 2, 2, 4\) \(3, 6, 6, 6, 6\) \(0 + 0 + 4 + 4 + 2 = 10\)
\(3\) \(3, 6, 2, 7, 4\) \(3, 6, 6, 7, 7\) \(0 + 0 + 4 + 0 + 3 = 7\)
\(4\) \(4, 6, 2, 7, 4\) \(4, 6, 6, 7, 7\) \(0 + 0 + 4 + 0 + 3 = 7\)
Ulaz
3 4
3 1 1
3 1
2 2
1 2
2 1
Izlaz
3
1
5
4
Ulaz
3 2
1 3 1
3 1
2 1
Izlaz
1
2

Comments

There are no comments at the moment.