도시의 지평선

농부 존(Farmer John)이 소들을 데리고 도시로 여행을 왔습니다. 해가 지자, 소들은 도시의 지평선을 바라보며 직사각형 건물들이 만들어 내는 아름다운 실루엣을 감상합니다.

지평선 전체는 하나의 수직선으로 나타내며, 그 위에 $N$개의 건물이 서 있습니다 ($1 \le N \le 40{,}000$). $i$번째 건물의 실루엣은 지평선 위의 위치 $A_i$부터 $B_i$까지를 밑변으로 하고 ($1 \le A_i < B_i \le 1{,}000{,}000{,}000$), 높이는 $H_i$입니다 ($1 \le H_i \le 1{,}000{,}000{,}000$). 모든 건물은 지면($y = 0$) 위에 세워져 있습니다.

$N$개의 건물이 함께 만들어 내는 실루엣, 즉 모든 직사각형의 합집합이 덮는 넓이를 제곱 단위로 구하세요. 서로 겹치는 부분은 한 번만 세어야 합니다.

• 첫째 줄: 정수 $N$
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번째 건물을 나타내는 세 정수 $A_i$, $B_i$, $H_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄: $N$개의 건물이 만드는 실루엣 전체의 넓이(제곱 단위)

위 예제에서 첫 번째 건물과 네 번째 건물은 넓이 $1$만큼 겹칩니다. 겹치는 부분을 한 번만 세면 전체 넓이는 $3 \times 1 + 1 \times 4 + 2 \times 2 + 2 \times 3 - 1 = 16$이 됩니다.