Description

老鼠是個天才兒童，在三歲時養了一隻貓咪。
貓咪每天都會給老鼠 1kg 的起司，只是今天老鼠把起司放在磅秤上後，發現起司竟然少了 24g。

於是老鼠給了貓咪一個池塘，池塘裡有 $n$ 隻魚，編號為 $1 \sim n$ ，編號 $i$ （ $1 \leq i \leq n$ ）的魚大小為 $a_{i}$ 。
每隻魚的視力都不相同，能看到的範圍也各有差異，具體來說，編號 $i$ 的魚的可視範圍為 $[l_{i}, r_{i}]$ ，代表這隻魚可以看到編號 $l_{i} \sim r_{i}$ 的魚。

如果編號 $i$ 的魚的可視範圍內，有魚的大小比自己大，那牠就會太過自卑而翻白肚，也就是說，只要存在一個 $j$ ，滿足 $l_{i} \leq j \leq r_{i}$ ，且 $a_{j} > a_{i}$ ，那編號 $i$ 的魚就會翻白肚。
為了不讓任何一隻魚翻白肚，貓咪可以事先餵池塘裡的魚飼料，編號 $i$ 的魚吃了 $1$ 粒飼料後會讓 $a_{i}$ 增加 $1$ ，也就是大小會變大 $1$ 。

因為貓咪的池塘很大，一隻魚可以吃任意多粒的飼料。只是因為飼料很貴，貓咪想要使用盡量少粒的飼料，使得池塘裡沒有任何一隻魚翻白肚。
請幫幫貓咪計算最少要使用幾粒飼料，並輸出在餵完飼料後， $a_{1} \sim a_{n}$ 其中一組可能的解，使得沒有任何一隻魚翻白肚。

Input Format

第一行有一個正整數 $n$ ，代表魚的數量。
第二行有 $n$ 個正整數 $a_{1} \sim a_{n}$ ，代表每隻魚的大小。
接下來 $n$ 行，第 $i$ 行有兩個正整數 $l_{i}, r_{i}$ ，代表編號 $i$ 的魚的可視範圍。

對於所有測試資料：

$1 \leq n \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq 10^{9}$ （ $1 \leq i \leq n$ ）
$1 \leq l_{i} \leq r_{i} \leq n$ （ $1 \leq i \leq n$ ）

Output Format

輸出有兩行：

第一行輸出一個整數代表最少要使用幾粒飼料。
第二行輸出 $n$ 個以空白隔開的正整數，代表在使用最少的飼料不讓任何魚翻白肚後， $a_{1} \sim a_{n}$ 可以是多少。

若有多組解輸出其中一組即可，注意請滿足題目條件。

Sample Input 1

Sample Output 1

6
7 2 2 7

Hints

給編號 $2$ 的魚餵 $1$ 粒飼料，給編號 $4$ 的魚餵 $5$ 粒飼料，共使用 $6$ 粒飼料，並且是在滿足條件下使用的最少飼料數。

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	1~4	$l_{i} = 1, r_{i} = i$	7
3	1, 5~8	$n \leq 3000, r_{i} \leq i$	8
4	1~14, 19	$r_{i} \leq i$	22
5	1, 15~22	$l_{i} = r_{i}$	21
6	0~1, 15~26	$\sum_{i = 1}^{n} (r_{i} - l_{i} + 1) \leq 5 \times 10^{5}$	16
7	0~45	無其他限制	26

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	2500	262144	65536	1 6 7
1	2500	262144	65536	2 3 4 5 6 7
2	2500	262144	65536	2 4 7
3	2500	262144	65536	2 4 7
4	2500	262144	65536	2 4 7
5	2500	262144	65536	3 4 7
6	2500	262144	65536	3 4 7
7	2500	262144	65536	3 4 7
8	2500	262144	65536	3 4 7
9	2500	262144	65536	4 7
10	2500	262144	65536	4 7
11	2500	262144	65536	4 7
12	2500	262144	65536	4 7
13	2500	262144	65536	4 7
14	2500	262144	65536	4 7
15	2500	262144	65536	5 6 7
16	2500	262144	65536	5 6 7
17	2500	262144	65536	5 6 7
18	2500	262144	65536	5 6 7
19	2500	262144	65536	4 5 6 7
20	2500	262144	65536	5 6 7
21	2500	262144	65536	5 6 7
22	2500	262144	65536	5 6 7
23	2500	262144	65536	6 7
24	2500	262144	65536	6 7
25	2500	262144	65536	6 7
26	2500	262144	65536	6 7
27	2500	262144	65536	7
28	2500	262144	65536	7
29	2500	262144	65536	7
30	2500	262144	65536	7
31	2500	262144	65536	7
32	2500	262144	65536	7
33	2500	262144	65536	7
34	2500	262144	65536	7
35	2500	262144	65536	7
36	2500	262144	65536	7
37	2500	262144	65536	7
38	2500	262144	65536	7
39	2500	262144	65536	7
40	2500	262144	65536	7
41	2500	262144	65536	7
42	2500	262144	65536	7
43	2500	262144	65536	7
44	2500	262144	65536	7
45	2500	262144	65536	7

Submit out of contest

2319 . 貓咪與老鼠