{"raw_statement":[{"iden":"statement","content":"The christmas spirit is taking over the city of Arcoverde! In honor of this special day, the mayor of this renowned metropolis decided to decorate all of the city's front view. To do this, he asked his engineer friends Icaro and Cortizo how much it would cost.\n\nIt is known that the mayor likes to save as much money as possible. Therefore, Icaro and Cortizo need to find out what is the minimum area necessary to comprise the entire city's front view.\n\nArcoverde is made only of rectangular buildings, in two dimensions, and all buildings were built on the same base height, as shown on the picture below.\n\nIcaro and Cortizo were very tired, since they were also responsible for building the biggest christmas tree ever seen on Pernambuco, so they asked for your help.\n\nThe first input line contains an integer $N$($1 <= N <= 10^5$), indicating the number of buildings in Arcoverde. Then, $N$ lines follow, each one containing three integers $L_i$ ($0 <= L_i < 10^9$), $R_i$ ($L_i < R_i <= 10^9$) and $H_i$ ($1 <= H_i <= 10^6$), which are, respectively, the left X-coordinate, the right X-coordinate and the height of the $i$-th building.\n\nThe output consists in a single integer number, which is the minimum area required to decorate the entire front view of Arcoverde.\n\n"},{"iden":"input","content":"The first input line contains an integer $N$($1 <= N <= 10^5$), indicating the number of buildings in Arcoverde. Then, $N$ lines follow, each one containing three integers $L_i$ ($0 <= L_i < 10^9$), $R_i$ ($L_i < R_i <= 10^9$) and $H_i$ ($1 <= H_i <= 10^6$), which are, respectively, the left X-coordinate, the right X-coordinate and the height of the $i$-th building."},{"iden":"output","content":"The output consists in a single integer number, which is the minimum area required to decorate the entire front view of Arcoverde."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of buildings.  \nFor each building $ i \\in \\{1, \\dots, N\\} $, define:  \n- $ L_i \\in \\mathbb{Z} $: left x-coordinate,  \n- $ R_i \\in \\mathbb{Z} $: right x-coordinate, with $ L_i < R_i $,  \n- $ H_i \\in \\mathbb{Z}^+ $: height.  \n\nEach building is represented as a rectangle $ [L_i, R_i] \\times [0, H_i] $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 0 \\leq L_i < R_i \\leq 10^9 $  \n3. $ 1 \\leq H_i \\leq 10^6 $\n\n**Objective**  \nCompute the area of the union of all rectangles:  \n$$\n\\text{Area} = \\int_{x=-\\infty}^{\\infty} \\max_{i: L_i \\leq x < R_i} H_i \\, dx\n$$  \nEquivalently, compute the area of the skyline formed by overlapping rectangles aligned on the x-axis, where at each x-coordinate, the height is the maximum height of any building covering that x.","simple_statement":"Given N rectangular buildings with left, right, and height, find the total area of the skyline formed by overlapping buildings.","has_page_source":false}