CF1572F Stations

There are $ n $ cities in a row numbered from $ 1 $ to $ n $ . The cities will be building broadcasting stations. The station in the $ i $ -th city has height $ h_i $ and range $ w_i $ . It can broadcast information to city $ j $ if the following constraints are met: - $ i \le j \le w_i $ , and - for each $ k $ such that $ i < k \le j $ , the following condition holds: $ h_k < h_i $ . In other words, the station in city $ i $ can broadcast information to city $ j $ if $ j \ge i $ , $ j $ is in the range of $ i $ -th station, and $ i $ is strictly highest on the range from $ i $ to $ j $ (including city $ j $ ).At the beginning, for every city $ i $ , $ h_i = 0 $ and $ w_i = i $ . Then $ q $ events will take place. During $ i $ -th event one of the following will happen: - City $ c_i $ will rebuild its station so that its height will be strictly highest among all stations and $ w_{c_i} $ will be set to $ g_i $ . - Let $ b_j $ be the number of stations that can broadcast information to city $ j $ . Print the sum of $ b_j $ over all $ j $ satisfying $ l_i \le j \le r_i $ . Your task is to react to all events and print answers to all queries.

N/A

N/A

In the first test case, only station $ 1 $ reaches city $ 1 $ before and after it is rebuilt. In the second test case, after each rebuild, the array $ b $ looks as follows: 1. $ [1, 1, 1, 2, 1] $ ; 2. $ [1, 2, 2, 3, 2] $ ; 3. $ [1, 2, 2, 1, 2] $ ; 4. $ [1, 1, 2, 1, 2] $ ; 5. $ [1, 1, 2, 1, 1] $ .