Aoi có \(N\) lá bài được đánh số từ \(1\) đến \(N\). Trên mỗi lá bài ghi một số nguyên dương; số trên lá bài thứ \(i\) (\(1\le i\le N\)) là \(A_i\).

Aoi sẽ chơi \(Q\) ván bằng các lá bài và một chiếc bảng. Ván thứ \(j\) (\(1\le j\le Q\)) gồm các bước sau:

1. Viết số \(0\) lên bảng.
2. Xếp các lá bài \(L_j,L_j+1,\ldots,R_j\) trên bàn từ trái sang phải theo đúng thứ tự này.
3. Thực hiện \(R_j-L_j+1\) thao tác. Ở thao tác thứ \(k\) (\(1\le k\le R_j-L_j+1\)), gọi \(x\) là số hiện trên bảng và \(y\) là số trên lá bài thứ \(k\) từ trái sang. Xóa \(x\) rồi viết một trong hai số \(x+y\) hoặc \(x-y\) lên bảng. Nếu chọn \(x-y\), Aoi được ăn một miếng uiro, một loại bánh ngọt truyền thống của Nhật Bản. Tuy nhiên, không được viết số nhỏ hơn \(0\) lên bảng.

Cho thông tin về các lá bài và các ván chơi, hãy tìm số miếng uiro nhiều nhất Aoi có thể ăn trong mỗi ván.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).
• Dòng thứ ba chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(L_j,R_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa số miếng uiro nhiều nhất Aoi có thể ăn trong ván thứ \(j\).

Ràng buộc

• \(1\le N\le 200000\).
• \(1\le A_i\le 100\) (\(1\le i\le N\)).
• \(1\le Q\le 200000\).
• \(1\le L_j\le R_j\le N\) (\(1\le j\le Q\)).
• Tất cả giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(3\) điểm: \(N\le 20\), \(Q\le 20\).
2. \(5\) điểm: \(N\le 300\), \(Q\le 20\).
3. \(7\) điểm: \(N\le 5000\), \(Q\le 20\).
4. \(15\) điểm: \(Q\le 20\).
5. \(21\) điểm: \(A_i\le 2\) với mọi \(1\le i\le N\).
6. \(29\) điểm: \(A_i\le 20\) với mọi \(1\le i\le N\).
7. \(20\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
3 4 7 2 8
2
1 3
4 4

1
0

14
1 2 2 1 2 1 1 2 1 2 2 1 1 1
5
1 2
1 14
5 11
3 12
4 7

0
8
4
6
2

8
16 23 45 76 43 97 12 43
7
1 8
3 7
2 7
4 5
5 8
2 6
3 5

3
2
2
1
2
2
1

Nguồn

Bài Uiro, JOI 2024/2025, kỳ thi thứ tư của vòng tuyển chọn mùa xuân, do Ủy ban Olympic Tin học Nhật Bản (Japanese Committee for the International Olympiad in Informatics, JCIOI) công bố theo giấy phép CC BY-SA 4.0. Đây là bản dịch tiếng Việt của đề chính thức.