Когда в очередной раз на уроке физкультуры дети не смогли сразу выстроиться по росту и это заняло 5 минут занятия, физрук придумал новое правило. Дети заходят все вместе и сразу встают в ряд. После этого могут меняться местами только два школьника, стоящих рядом. При этом они, конечно же, должны отжаться столько раз, какая у них оказалась разница в росте. Сколько раз в результате суммарно отожмутся школьники, прежде чем у них получится выстроиться по росту в порядке убывания?
Формат входных данных
В первой строке число содержится число N (2 <= N <= 1000) количество детей в классе. В
следующей строке записана исходная расстановка школьников: N чисел через пробел, i-е число
обозначает рост i-го школьника ri (1 <= ri <= 109) в нанометрах.
Формат выходных данных
Одно число суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 109 раз.
Замечание
В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).