CF444E DZY Loves Planting

DZY loves planting, and he enjoys solving tree problems. DZY has a weighted tree (connected undirected graph without cycles) containing $ n $ nodes (they are numbered from $ 1 $ to $ n $ ). He defines the function $ g(x,y) $ $ (1

The first line contains an integer $ n (1

Print a single integer representing the answer.

In the first sample, one of the optimal $ p $ is $ [4,3,2,1] $ .