Орехус живет в доме с \(n\) этажами. На \(i\)-м этаже живут \(a_i\) людей. Каждый житель пользуется лифтом два раза в день: чтобы добраться со своего этажа на первый, и, чтобы добраться с первого на свой, когда возвращается домой.
Было решено, что, когда лифт не работает, он всегда будет стоять на \(x\)-м этаже, но \(x\) пока не выбрали. Когда какому-то жителю надо добраться с этажа \(a\) на этаж \(b\), лифт действует по следующему алгоритму:
- Перемещается с \(x\)-го этажа (изначально лифт стоит на \(x\)-м этаже) на \(a\)-й и забирает пассажира.
- Перемещается с \(a\)-го этажа на \(b\)-й и выпускает пассажира (если \(a\) равен \(b\), то лифт все равно приезжает на нужный этаж с \(x\)-го).
- Перемещается с \(b\)-го этажа обратно на \(x\)-й и ждет там следующего вызова.
Лифт никогда не перемещает более одного человека и всегда возвращается пустым на
\(x\)-й этаж перед тем, как начать перемещать следующего пассажира. Лифт тратит одну единицу энергии, чтобы переместиться между соседними этажами. Следовательно, чтобы переместиться с
\(a\)-го этажа на
\(b\)-й, необходимо
\(|a - b|\) единиц энергии.
Ваша задача помочь Орехусу найти минимальное число единиц энергии, которой хватит на один целый день, выбрав оптимальный \(x\)-й этаж. Не забудьте, что лифт начинает и заканчивает на \(x\)-м этаже.
Примечание
В первом примере, если в качестве этажа \(x\) выбрать второй, то двое жителей второго этажа за день потратят по \(4\) единицы энергии каждый (\(2\), чтобы спуститься вниз, и \(2\), чтобы подняться наверх), а единственный житель третьего этажа потратит \(8\) за день (\(4\), чтобы спуститься вниз, и \(4\), чтобы подняться наверх). \(4 \cdot 2 + 8 \cdot 1 = 16\).
Во втором примере оптимальный ответ достигается при выборе первого этажа в качестве \(x\)-го.