Bài tập

Số nguyên \(d\) là ước đặc biệt của số nguyên dương \(n\) khi \(1 < d < n\) và khi chia \(n\) cho \(d\) thì thương và số dư bằng nhau.

Ví dụ: \(3\) là ước đặc biệt của \(8\) bởi khi chia \(8\) cho \(3\) ta được thương là \(2\) và số dư khi chia \(8\) cho \(3\) cũng là \(2\).

Theo định nghĩa, nếu \(d\) là ước đặc biệt của \(n\) thì \(d\) không nhất thiết phải là một ước của \(n\).

Yêu cầu: Cho hai số nguyên dương \(a\) và \(b\) \((a \leq b)\), hãy tính tổng số lượng ước đặc biệt của tất cẩ các số \(n\) trong đoạn nguyên \([a, b]\).

Input

Gồm một dòng chứa hai số nguyên \(a, b\) \((1 < a \leq b < 300000, b - a < 300000)\), các số ghi cách nhau dấu cách.

Output

Gồm một dòng ghi một số là tổng số ước đặc biệt của tất cả các số trong đoạn \([a, b]\).

Example

15 17

5

4 8

6

Scoring

\(50\%\) số test tương ứng với \(50\%\) số điểm có \(1 < b - a < 15000\).

Công ty Logistics ABC đang quản lý một dây chuyền đóng gói hàng hóa. Mỗi lượt, có \(n\) kiện hàng được xếp liên tiếp nhau, với kiện hàng thứ \(i\) có giá trị là \(a_i\). Để thuận tiện cho việc vận chuyển, các kiện hàng cần được chia thành \(k\) lô hàng. Mỗi lô hàng bao gồm một số kiện liên tiếp trên dây chuyền, và mỗi kiện hàng chỉ thuộc về đúng một lô. Tổng giá trị của các kiện hàng trong mỗi lô không được vượt quá một giới hạn cho trước là \(c\).

Sau khi chia lô, công ty cần đánh giá chất lượng của mỗi lô bằng cách tìm kiện hàng có giá trị lớn nhất. Tổng giá trị của các kiện hàng lớn nhất này từ tất cả các lô được gọi là điểm số \(s\).

Yêu cầu: Với mỗi giới hạn \(c\) được đưa ra, hãy giúp công ty tìm cách chia \(n\) kiện hàng thành một số lô nhỏ nhất có thể (\(k\) nhỏ nhất). Trong số các cách chia có cùng số lô nhỏ nhất này, hãy chọn cách chia mang lại điểm số \(s\) lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).
• Dòng thứ ba chứa một số nguyên \(q\) (\(1 \le q \le 10\)) là số lượng truy vấn.
• Mỗi dòng trong số \(q\) dòng tiếp theo tương ứng với một truy vấn chứa một số nguyên \(c\) (\(\max(a_1, a_2, \ldots, a_n) \le c \le 10^{10}\)).

Output

• Gồm \(q\) dòng, mỗi dòng tương ứng với một truy vấn, in ra hai số nguyên \(k\) và \(s\) tìm được.

Example

5
5 3 2 2 5
2
9
8

2 10
3 13

Scoring

• Subtask 1 (20% số điểm): \(n \le 20\).
• Subtask 2 (20% số điểm): \(n \leq 100\).
• Subtask 3 (20% số điểm): \(a_1 \ge a_2 \ge \ldots \ge a_n\).
• Subtask 4 (10% số điểm): \(k \leq 3\).
• Subtask 5 (10% số điểm): \(c \leq 100\).
• Subtask 6 (20% số điểm): Không có ràng buộc gì thêm.

Cho dãy số nguyên dương gồm \(n\) số hạng \(a_1, a_2, \dots, a_n\).

Yêu cầu: Có \(q\) truy vấn, mỗi truy vấn gồm hai chỉ số \(l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq i \leq q)\) yêu cầu trả lời trong đoạn con \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\) có bao nhiêu số hạng khác nhau.

Input

Dữ liệu vào từ tệp văn bản CAU4.INP gồm:

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9, 1 \leq i \leq n)\).
• Dòng thứ ba chứa số nguyên \(q\) \((1 \leq q \leq 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq i \leq q)\) tương ứng với một truy vấn.

Các số trên một dòng cách nhau đúng một dấu cách.

Output

Ghi ra tệp văn bản CAU4.OUT gồm:

• Tương ứng với mỗi truy vấn, in ra một dòng chứa một số là kết quả của truy vấn đó.

Example

9
33 5 6 7 8 112 6 6 6
4
1 9
2 7
5 9
3 4

6
5
3
2

Scoring

• 30% số điểm có \(n \leq 10^4, q \leq 10^4\).
• 30% số điểm có \(n \leq 10^4, q \leq 10^5\).
• 40% số điểm có \(n \leq 10^5, q \leq 10^5\).

Bạn được trao một mảng số nguyên \(d_1, d_2, \dots, d_n\) gồm \(n\) số nguyên. Hãy tưởng tượng bạn đang tham gia một trò chơi số học, nơi bạn cần tìm cách chia mảng này thành ba phần (một số phần có thể rỗng) sao cho mỗi phần tử của mảng thuộc về đúng một trong ba phần và mỗi phần tạo thành một đoạn liên tiếp (có thể rỗng) của mảng ban đầu.

Gọi tổng các phần tử của phần thứ nhất là $sum_1$, tổng các phần tử của phần thứ hai là $sum_2$ và tổng các phần tử của phần thứ ba là $sum_3$. Trong tất cả các cách chia mảng, bạn cần chọn một cách sao cho $sum_1 = sum_3$ và giá trị $sum_1$ lớn nhất có thể.

Cụ thể hơn, nếu phần thứ nhất của mảng chứa $a$ phần tử, phần thứ hai chứa $b$ phần tử và phần thứ ba chứa $c$ phần tử, ta có:

• \(sum_1 = \sum_{1 \leq i \leq a} d_i\)
• \(sum_2 = \sum_{a+1 \leq i \leq a+b} d_i\)

• \(sum_3 = \sum_{a+b+1 \leq i \leq a+b+c} d_i\)

  Tổng của một mảng rỗng được xem là 0.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) --- số phần tử của mảng \(d\).
• Dòng thứ hai chứa \(n\) số nguyên \(d_1, d_2, \dots, d_n\) (\(1 \leq d_i \leq 10^9\)) --- các phần tử của mảng.

Output

• In ra một số nguyên duy nhất --- giá trị lớn nhất có thể của \(sum_1\), thỏa mãn điều kiện \(sum_1 = sum_3\).

  Rõ ràng, luôn tồn tại ít nhất một cách chia hợp lệ (sử dụng \(a = c = 0\) và \(b = n\)).

Example

5
1 3 1 1 4

5

5
1 3 2 1 4

4

3
4 1 2

0

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 1000\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.