CF212D Cutting a Fence

Vasya the carpenter has an estate that is separated from the wood by a fence. The fence consists of $ n $ planks put in a line. The fence is not closed in a circle. The planks are numbered from left to right from 1 to $ n $ , the $ i $ -th plank is of height $ a_{i} $ . All planks have the same width, the lower edge of each plank is located at the ground level. Recently a local newspaper "Malevich and Life" wrote that the most fashionable way to decorate a fence in the summer is to draw a fuchsia-colored rectangle on it, the lower side of the rectangle must be located at the lower edge of the fence. Vasya is delighted with this idea! He immediately bought some fuchsia-colored paint and began to decide what kind of the rectangle he should paint. Vasya is sure that the rectangle should cover $ k $ consecutive planks. In other words, he will paint planks number $ x $ , $ x+1 $ , $ ... $ , $ x+k-1 $ for some $ x $ $ (1

N/A

N/A

Let's consider the first sample test. - There are three possible positions of the fence for $ k_{1}=1 $ . For the first position $ (x=1) $ the height is 3, for the second one $ (x=2) $ the height is 2, for the third one $ (x=3) $ the height is 1. As the fence position is chosen uniformly, the expected height of the fence equals ; - There are two possible positions of the fence for $ k_{2}=2 $ . For the first position $ (x=1) $ the height is 2, for the second one $ (x=2) $ the height is 1. The expected height of the fence equals ; - There is the only possible position of the fence for $ k_{3}=3 $ . The expected height of the fence equals 1.