Đường chân trời (SKYLINE)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Các tòa nhà được đặt từ sau ra trước. Với mỗi tòa nhà, tính tổng chiều dài phần có chiều cao không thấp hơn đường chân trời phía sau, rồi cập nhật đường chân trời.

Input

Dòng đầu chứa số tòa nhà $n$. Mỗi trong $n$ dòng tiếp theo chứa $l_i,r_i,h_i$. Tòa nhà phủ đoạn ngang nửa mở $[l_i,r_i)$ và có chiều cao $h_i$. Các tòa nhà được cho theo thứ tự từ sau ra trước.

Output

In một số nguyên: tổng overlap của tất cả tòa nhà. Tại mỗi vị trí, phần của tòa nhà hiện tại được tính nếu $h_i$ lớn hơn hoặc bằng độ cao skyline trước khi đặt tòa nhà.

Subtask

• 20 điểm: $n\le50$.
• 30 điểm: $n\le5000$.
• 50 điểm: $1\le n<10^5$, $0<l_i<r_i\le10^5$, $0<h_i\le10^9$; tổng overlap không vượt $2\cdot10^6$.

Ví dụ

Input

3
5 11 3
1 10 1
3 13 2

Output

14

Giải thích

Tòa nhà thứ nhất đóng góp chiều dài 6. Tòa nhà thứ hai chỉ cao ít nhất skyline trên đoạn $[1,5)$ nên đóng góp 4. Tòa nhà thứ ba hợp lệ trên $[3,5)$ và $[11,13)$, tổng 4. Kết quả là $6+4+4=14$.