Server Time:

User's AC Ratio in this contest

20.0% (4/20)

Submission's AC Ratio in this contest

4.8% (4/84)

Description

偉杰是個很忙的人,他該睡覺了

偉杰這陣子有許多事情要做,例如:
去數石頭解保險箱的密碼打 BNT整理紙本帳務吃牛肉麵等等
喔對了,還有出題目

其中有些事情會讓他快樂,有些事情不快樂
遇到快樂的事情就會增加快樂值;不快樂的事情就會減少快樂值
某一天他打算翹掉一部分的行程,直接去睡覺

偉杰會給你行程表 $A$,且一開始快樂值 $h$ 為 $0$
問你若某段行程 $[l, r]$ 去睡覺,那天最高與最低的 $h$ 為多少?
這樣可以讓他考慮是否該在這段行程睡覺

例如行程表 $A = (+1, -2, +3, +4, -7, +9)$
若行程 $[3, 5]$ 去睡覺,則行程剩 $(+1, -2, +9)$,$h$ 從頭到尾的變化為 $0 \overset{+1}{\longrightarrow} 1 \overset{-2}{\longrightarrow} -1 \overset{+9}{\longrightarrow} 8$
所以這之中 $h$ 最低為 $-1$ 且最高為 $8$

Input Format

第一列給定 $n, m$ 表示行程表長度以及偉杰總共問幾次,$(1 \le n, m \le 5\cdot 10^5)$
第二列給定長度 $n$ 的行程表 $A$,$(|A_i| \le 20)$
接著給 $m$ 列 $l, r$ 表示行程 $l$ 到 $r$ 去睡覺,$(1\le l \le r \le n)$

Output Format

輸出兩個數字,表示 $h$ 的最低值以及最高值

Sample Input 1

8 3
-1 1 -1 -1 1 -1 -1 1
2 5
2 8
1 8

Sample Output 1

-3 0
-1 0
0 0

Sample Input 2

6 4
1 -2 3 4 -7 9
3 5
4 6
1 1
1 4

Sample Output 2

-1 8
-1 2
-2 7
-7 2

Hints

第一筆範測對於每個詢問,剩下的行程表分別為:

  1. $(-1, -1, -1, +1)$
  2. $(-1)$
  3. $()$

則 $h$ 的變化分別為:

  1. $h = 0 \overset{-1}{\longrightarrow} -1 \overset{-1}{\longrightarrow} -2 \overset{-1}{\longrightarrow} -3 \overset{+1}{\longrightarrow} -2$
  2. $h = 0 \overset{-1}{\longrightarrow} -1$
  3. $h = 0$





Problem Source

CODEFORCES 1473D Program

Subtasks

No. Testdata Range Score
1 0~24 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1