Constellation 3

Time limit1sMemory limit512 MB

Summary

Given a histogram of white building columns and weighted yellow star pixels, find the minimum total cost of removing stars so no rectangle free of buildings contains two or more stars.

Level: Hard9 of 10
Topics: Divide and conquer, Dynamic programming, Segment tree
Solved: No attempts yet

Statement

JOI-kun took a picture of the night view. The picture consists of $N \times N$ pixels, that is, $N$ pixels along the horizontal and vertical directions. The pixel in the $x$ -th column from the left and the $y$ -th row from the bottom ( $1 \le x \le N$ , $1 \le y \le N$ ) is called the pixel $(x, y)$ .

Each pixel shows a building, the night sky, or a star. Its color is white, black, or yellow, respectively.

For each $i$ with $1 \le i \le N$ , in the $i$ -th column, the pixels from the bottommost row up to the $A_i$ -th row from the bottom are white pixels showing buildings. There are $M$ yellow pixels showing stars. The $j$ -th yellow pixel ( $1 \le j \le M$ ) is the pixel $(X_j, Y_j)$ . All other pixels are black pixels showing the night sky.

A rectangular region of the picture shows a constellation if both of the following conditions hold.

There is no white pixel in the rectangular region.
There are two or more yellow pixels in the rectangular region.

JOI-kun is tired of watching constellations. By painting some yellow pixels black, he wants to make a picture in which no rectangular region shows a constellation. However, painting many yellow pixels makes the picture unnatural. Specifically, if he paints the $j$ -th yellow pixel ( $1 \le j \le M$ ) black, the unnatural level of the picture increases by $C_j$ . Initially the unnatural level is 0.

Given the picture and the value $C_j$ for each yellow pixel, find the minimum unnatural level of the picture after painting some yellow pixels so that no rectangular region shows a constellation.

Input

The input is given in the following format.

N
A_1 A_2 \cdots A_N
M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

All values are integers.

Output

Print one line containing the minimum unnatural level after painting some yellow pixels so that no rectangular region shows a constellation.

Constraints

$1 \le N \le 200\,000$ .
$1 \le A_i \le N$ ( $1 \le i \le N$ ).
$1 \le M \le 200\,000$ .
$1 \le X_j \le N$ ( $1 \le j \le M$ ).
$1 \le Y_j \le N$ ( $1 \le j \le M$ ).
$1 \le C_j \le 1\,000\,000\,000$ ( $1 \le j \le M$ ).
$A_{X_j} < Y_j$ ( $1 \le j \le M$ ).
$(X_j, Y_j) \ne (X_k, Y_k)$ ( $1 \le j < k \le M$ ).

Examples3

Example 1
Input
```
5
1 3 4 2 3
3
1 5 3
4 3 2
2 4 2
```
Expected output
```
2
```

Example 2

Input

7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8

Expected output

Example 3

Input

8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

Expected output