Universal Cup Judging System

Universal Cup

Límite de tiempo: 5.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Ti viene dato un array $a$ composto da $n$ interi positivi. Tuttavia, alcuni elementi di $a$ sono mancanti e sono stati sostituiti da zeri.

Definisci l'oscillazione di $a$ su un segmento $[\ell, r]$ come $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

Ti vengono dati $q$ segmenti nella forma $[\ell_i, r_i]$. Sostituisci ogni zero in $a$ con un intero positivo per minimizzare la somma delle oscillazioni di $a$ su tutti i $q$ segmenti.

Input

La prima riga contiene due interi $n$ e $q$ ($1 \le n, q \le 2 \cdot 10^5$).

La seconda riga contiene $n$ interi $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): gli elementi dell'array. Qui, $a_i = 0$ significa che l'$i$-esimo elemento è mancante.

Le successive $q$ righe descrivono i segmenti. Ciascuna di esse contiene due interi $\ell_i$ e $r_i$ ($1 \le \ell_i \le r_i \le n$).

Output

Stampa un singolo intero: la somma minima delle oscillazioni di $a$ su tutti i segmenti dati.

Esempi

Input 1

5 2
2 1 0 3 2
1 3
3 5

Output 1

2

Input 2

5 3
1 0 3 0 1
1 2
2 4
5 5

Output 2

2

Input 3

7 4
4 4 0 1 0 3 4
1 3
1 3
3 5
4 7

Output 3

6

Note

Nel primo esempio, l'unico array ottimale è $a = [2, 1, 2, 3, 2]$.

Nel secondo esempio, ci sono diversi array ottimali. Ad esempio, $a = [1, 2, 3, 2, 1]$ è ottimale.

Nel terzo esempio, ci sono diversi array ottimali. Ad esempio, $a = [4, 4, 4, 1, 2, 3, 4]$ è ottimale.

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.