CF650D Zip-line

Vasya has decided to build a zip-line on trees of a nearby forest. He wants the line to be as long as possible but he doesn't remember exactly the heights of all trees in the forest. He is sure that he remembers correct heights of all trees except, possibly, one of them. It is known that the forest consists of $ n $ trees staying in a row numbered from left to right with integers from $ 1 $ to $ n $ . According to Vasya, the height of the $ i $ -th tree is equal to $ h_{i} $ . The zip-line of length $ k $ should hang over $ k $ ( $ 1

N/A

N/A

Consider the first sample. The first assumption actually coincides with the height remembered by Vasya. In the second assumption the heights of the trees are $ (4,2,3,4) $ , in the third one they are $ (1,2,3,3) $ and in the fourth one they are $ (1,2,3,5) $ .