CF922D Robot Vacuum Cleaner

Pushok the dog has been chasing Imp for a few hours already. :::align{center}  ::: Fortunately, Imp knows that Pushok is afraid of a robot vacuum cleaner. While moving, the robot generates a string $ t $ consisting of letters 's' and 'h', that produces a lot of noise. We define noise of string $ t $ as the number of occurrences of string "sh" as a subsequence in it, in other words, the number of such pairs $ (i,j) $ , that $ i

The first line contains a single integer $ n $ ( $ 1

Print a single integer — the maxumum possible noise Imp can achieve by changing the order of the strings.

The optimal concatenation in the first sample is $ ssshhshhhs $ .