CF675E Trains and Statistic

Vasya commutes by train every day. There are $ n $ train stations in the city, and at the $ i $ -th station it's possible to buy only tickets to stations from $ i+1 $ to $ a_{i} $ inclusive. No tickets are sold at the last station. Let $ ρ_{i,j} $ be the minimum number of tickets one needs to buy in order to get from stations $ i $ to station $ j $ . As Vasya is fond of different useless statistic he asks you to compute the sum of all values $ ρ_{i,j} $ among all pairs $ 1

N/A

N/A

In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is $ 6 $ , so the answer is also $ 6 $ . Consider the second sample: - $ ρ_{1,2}=1 $ - $ ρ_{1,3}=2 $ - $ ρ_{1,4}=3 $ - $ ρ_{1,5}=3 $ - $ ρ_{2,3}=1 $ - $ ρ_{2,4}=2 $ - $ ρ_{2,5}=2 $ - $ ρ_{3,4}=1 $ - $ ρ_{3,5}=1 $ - $ ρ_{4,5}=1 $ Thus the answer equals $ 1+2+3+3+1+2+2+1+1+1=17 $ .