utils/scrapers/prescraped/codeforces/Problems/1474E

Lunar rover finally reached planet X. After landing, he met an obstacle, that contains permutation p of length n. Scientists found out, that to overcome an obstacle, the robot should make p an identity permutation (make pi=i for all i).Unfortunately, scientists can't control the robot. Thus the only way to make p an identity permutation is applying the following operation to p multiple times:   Select two indices i and j (i≠j), such that pj=i and swap the values of pi and pj. It takes robot (j−i)2 seconds to do this operation.  Positions i and j are selected by the robot (scientists can't control it). He will apply this operation while p isn't an identity permutation. We can show that the robot will make no more than n operations regardless of the choice of i and j on each operation.Scientists asked you to find out the maximum possible time it will take the robot to finish making p an identity permutation (i. e. worst-case scenario), so they can decide whether they should construct a new lunar rover or just rest and wait. They won't believe you without proof, so you should build an example of p and robot's operations that maximizes the answer.For a better understanding of the statement, read the sample description.