CF1151E Number of Components

The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of $ n $ vertices. Each vertex $ i $ has its own value $ a_i $ . All vertices are connected in series by edges. Formally, for every $ 1 \leq i < n $ there is an edge between the vertices of $ i $ and $ i+1 $ . Denote the function $ f(l, r) $ , which takes two integers $ l $ and $ r $ ( $ l \leq r $ ): - We leave in the tree only vertices whose values ​​range from $ l $ to $ r $ . - The value of the function will be the number of connected components in the new graph. Your task is to calculate the following sum: $ $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $ $$$

N/A

N/A

In the first example, the function values ​​will be as follows: - $ f(1, 1)=1 $ (there is only a vertex with the number $ 2 $ , which forms one component) - $ f(1, 2)=1 $ (there are vertices $ 1 $ and $ 2 $ that form one component) - $ f(1, 3)=1 $ (all vertices remain, one component is obtained) - $ f(2, 2)=1 $ (only vertex number $ 1 $ ) - $ f(2, 3)=2 $ (there are vertices $ 1 $ and $ 3 $ that form two components) - $ f(3, 3)=1 $ (only vertex $ 3 $ ) Totally out $ 7 $ .In the second example, the function values ​​will be as follows: - $ f(1, 1)=1 $ - $ f(1, 2)=1 $ - $ f(1, 3)=1 $ - $ f(1, 4)=1 $ - $ f(2, 2)=1 $ - $ f(2, 3)=2 $ - $ f(2, 4)=2 $ - $ f(3, 3)=1 $ - $ f(3, 4)=1 $ - $ f(4, 4)=0 $ (there is no vertex left, so the number of components is $ 0 $ ) Totally out $ 11 $ .