Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

Hai la capacità di creare robot di altezza compresa in $[0, d]$. Per testarli, hai costruito un percorso lineare di lunghezza $n$ contenente alcuni ostacoli. La descrizione degli ostacoli ti viene fornita come un array $a$. Se $a_i = 0$, allora non c'è alcun ostacolo nella $i$-esima posizione; altrimenti, c'è un ostacolo di altezza $a_i > 0$.

Per testare il tuo robot, selezioni un segmento $[l, r]$ e lo fai correre attraverso tutti gli ostacoli contenuti nel segmento. Quando il robot incontra un ostacolo con valore $a_i > 0$, si verifica una delle due possibilità:

  • Se l'altezza attuale del robot $h$ è minore di $a_i$, allora non succede nulla poiché il robot è troppo basso per raggiungere l'ostacolo.
  • Se l'altezza attuale del robot $h$ è almeno $a_i$, allora la nuova altezza diventa $h' = h - a_i$.

Ora devi rispondere a $q$ query. Per ciascuno dei $q$ segmenti $[l_i, r_i]$, devi determinare la massima altezza possibile con cui il robot può terminare il percorso dopo aver attraversato gli ostacoli nel segmento, scegliendo l'altezza iniziale nell'intervallo $[0, d]$.

Input

La prima riga contiene gli interi $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — la lunghezza dell'array e il numero di query.

La seconda riga contiene $n$ interi $a_i$ ($0 \le a_i \le 10^9$) — la descrizione dell'array.

Le successive $q$ righe contengono una coppia di interi $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — la descrizione delle query.

Output

Stampa $q$ interi — le risposte alle query.

Esempi

Input 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

Output 1

2
2
3

Input 2

7 5 10
7 6 2 5 0 1 4
1 3
1 7
4 7
2 5
4 6

Output 2

3
2
3
3
4

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#374EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.