Falling Fragments

In this problem, we study the splitting behavior of falling fragments produced by the Sixth Beast.

At the beginning, there are n points on the horizontal line y = 10^9 at positions \( (x_i,10^9) \) (\( 1 \le i \le n \)). These points start falling vertically downward (in the negative y‐direction). There are also m floating islands represented as horizontal line segments. The i-th island is given by the two endpoints \( (l_i,h_i) \) and \( (r_i,h_i) \) (note that it is possible that \( l_i = r_i \), in which case the island is a point). The islands are disjoint as geometric objects.

When a falling point touches an island, it is immediately captured by the island and splits into two new fragments. The two new fragments start from the left and right endpoints of that island, respectively, and resume falling vertically downward. (Even if the island is a point, it will split into two fragments.)

This process continues until the fragments have fallen all the way down to the x‐axis (i.e. y = 0). Your task is to compute the total number of fragments that eventually hit the x‐axis.

Note: When a fragment at \( (x,H) \) falls downward, if there exists one or more islands with \( h < H \) such that \( x \) is in the interval \( [l, r] \) of that island, the fragment will first encounter the island with the largest height among them. At that moment, the fragment splits into two, starting from \( (l, h) \) and \( (r, h) \), respectively. If no such island exists, the fragment directly reaches the ground and counts as one.

inputFormat

The first line contains two integers \( n \) and \( m \) — the number of initial points and the number of islands.

The second line contains \( n \) integers \( x_1, x_2, \ldots, x_n \): the x-coordinates of the initial falling points (each starting at \( y = 10^9 \)).

The following \( m \) lines each contain three integers \( l_i, r_i, h_i \). These denote an island with endpoints \( (l_i, h_i) \) and \( (r_i, h_i) \). It is allowed that \( l_i = r_i \).

Note: Islands do not overlap as entities.

outputFormat

Output a single integer — the total number of fragments that eventually hit the x-axis after all splitting processes.

sample

1 0
5

1