SKYLINE

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Buildings are added from back to front. For each building, count the horizontal length where its height is at least the skyline behind it, then update the skyline.

Input

The first line contains $n$. Each of the next $n$ lines contains $l_i,r_i,h_i$. The building covers the half-open horizontal interval $[l_i,r_i)$ at height $h_i$. Buildings are listed from back to front.

Output

Print one integer: the total overlap. At each horizontal position, the current building contributes if $h_i$ is at least the skyline height before inserting that building.

Subtasks

• 20 points: $n\le50$.
• 30 points: $n\le5000$.
• 50 points: $1\le n<10^5$, $0<l_i<r_i\le10^5$, $0<h_i\le10^9$; total overlap is at most $2\cdot10^6$.

Examples

Input

3
5 11 3
1 10 1
3 13 2

Output

14

Explanation

The first building contributes 6. The second contributes only on $[1,5)$, length 4. The third contributes on $[3,5)$ and $[11,13)$, another 4. Thus the total is $14$.