Description

OIVillage is a beautiful village. To better use its tourism resources, attract visitors, and boost the economy, xkszltl decided to build a railway connecting the $n$ most famous scenic spots so that tourists can take the train from the railway’s starting point (scenic spot 1) and visit each spot in order. To better evaluate this railway, xkszltl assigns each scenic spot a beauty value, and the value of a travel route is the sum of the beauty values of the scenic spots it passes through. However, as weather and seasons change, the beauty of some spots may change as well.

xkszltl hopes to provide the best travel guidance for every tourist. Because tourists have limited time, they may not be able to visit all spots, but they also do not want the trip to be too short. Therefore, each tourist wants to end their trip at some station within a certain interval, and xkszltl’s task is to choose an endpoint for them so that the travel route’s value is maximized. However, there are simply too many scenic spots and too many tourists, so xkszltl cannot finish in time and turns to you—who is aiming to ace NOI 2011—for help with this challenging task.

Input Format

• The first line contains an integer $n$. The next line contains $n$ integers, the initial beauty of each scenic spot.
• The third line contains an integer $m$. The next $m$ lines each describe one instruction:
  1. 0 x y k: Add $k$ to the beauty of every scenic spot from $x$ to $y$.
  2. 1 x y: One tourist wants to get off at some station in the interval $[x, y]$ (inclusive). You must tell them the maximum travel value.

The traveler always starts from scenic spot 1 and visits spots in order.

Output Format

For each query, output one integer: the maximum travel value.

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

9
22

Hint

$1 \le n, m \le 100000$.

$1 \le x \le y \le n$.

$|a_i|, |k| \le 10^9$.

Translated by ChatGPT 5