Universal Cup Judging System

Universal Cup

時間限制: 5.0 s 記憶體限制: 1024 MB 總分: 100 难度: [顯示] 可 Hack ✓
统计

$n$개의 양의 정수로 이루어진 배열 $a$가 주어집니다. 하지만 $a$의 일부 원소는 유실되어 0으로 대체되어 있습니다.

구간 $[\ell, r]$에서 배열 $a$의 진폭(oscillation)을 $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$로 정의합니다.

$[\ell_i, r_i]$ 형태의 구간 $q$개가 주어집니다. $a$에 있는 각 0을 양의 정수로 바꾸어, $q$개의 모든 구간에서 $a$의 진폭의 합을 최소화하세요.

입력

첫 번째 줄에는 두 정수 $n$과 $q$($1 \le n, q \le 2 \cdot 10^5$)가 주어집니다.

두 번째 줄에는 배열의 원소를 나타내는 $n$개의 정수 $a_1, \dots, a_n$($0 \le a_i \le 10^9$)이 주어집니다. 여기서 $a_i = 0$은 $i$번째 원소가 유실되었음을 의미합니다.

다음 $q$개의 줄에는 구간들이 설명됩니다. 각 줄에는 두 정수 $\ell_i$와 $r_i$($1 \le \ell_i \le r_i \le n$)가 주어집니다.

출력

주어진 모든 구간에서 $a$의 진폭의 합의 최솟값을 나타내는 정수 하나를 출력합니다.

예제

입력 1

5 2
2 1 0 3 2
1 3
3 5

출력 1

2

입력 2

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

출력 2

2

입력 3

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

출력 3

6

참고

첫 번째 예제에서 유일한 최적 배열은 $a = [2, 1, 2, 3, 2]$입니다.

두 번째 예제에서는 최적 배열이 여러 개 존재합니다. 예를 들어 $a = [1, 2, 3, 2, 1]$이 최적입니다.

세 번째 예제에서는 최적 배열이 여러 개 존재합니다. 예를 들어 $a = [4, 4, 4, 1, 2, 3, 4]$가 최적입니다.

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.