City Skyline Area Calculation

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows admire the beautiful silhouettes formed by the rectangular buildings along the horizon. The horizon is represented by a number line with \(N\) buildings. The \(i\)-th building spans the interval \([A_i, B_i)\) (with \(B_i\) exclusive) and has height \(H_i\). Initially, consider a number line (or array) with all values initialized to 0. For each building, every position in the interval \([A_i, B_i)\) is updated: if the current value is less than \(H_i\), it is replaced by \(H_i\). Equivalently, the final height at any point is the maximum \(H_i\) among all buildings covering that point.

The total area of the aggregate silhouette is then given by \(\sum_{\text{segment}} (\text{length of segment}) \times (\text{height})\), where the sum is taken over all maximal contiguous segments of equal height.

inputFormat

The first line contains an integer (N), the number of buildings. Each of the following (N) lines contains three space-separated integers: (A_i), (B_i), and (H_i), representing the left coordinate, right coordinate (exclusive), and height of the (i)-th building.

outputFormat

Output a single integer representing the total area of the aggregate silhouette.

sample

3
1 3 10
2 5 15
4 6 12

67