2025 ôn THT A - Buổi 24

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các giá trị của mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(-10 ^ 9 \leq x_i \leq 10 ^ 9\)

Example

Sample input

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

Sample output

9

Cho dãy số nguyên gồm n phần tử \(a_1,a_2,\cdots,a_n\) \((|a_i| \leq 10^9)\). Cho giá trị \(x\) và \(q\) câu hỏi có dạng \(S(u,v)\). Với \(S(u,v)\) là tổng các giá trị của các phần tử từ \(u\) đến \(v\).

Yêu cầu: Đếm xem trong \(q\) câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn \(x\).

Input

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

Output

• In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn \(x\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^5\)

Example

5 6 3
7 2 1 6 5
2 3
3 4
5 5 

2