В Васином городе есть n банков, расположенных по кругу так, что соседними являются банки, номера которых различаются на 1, а также банк номер 1 и банк номер n (если n > 1). При этом, сам себе банк соседом не является.
В каждом банке у Васи есть счёт с каким-нибудь балансом. Заметим, что он может быть и отрицательным, если Вася должен банку.
Васе доступна следующая операция: взять два соседних банка и перечислить со счёта в одном банке на счёт в другом любое количество денег. При этом нет никаких ограничений на размер переводимой суммы или текущее состояние счёта в любом из банков.
Вася путается в больших числах, поэтому он просит вас определить, за какое минимальное количество операций он может обнулить сумму денег, лежащую на счёте в каждом из банков. Гарантируется, что Вася может это сделать, то есть суммарный баланс Васи по всем банкам равен нулю.
Примечание
В первом примере можно перечислить из первого банка в третий сумму 5.
Во втором примере можно перечислить сначала из третьего банка во второй, а потом из второго в первый сумму 1.
В третьем примере одним из оптимальных ответов является следующая последовательность действий:
- перечислить из первого банка во второй сумму 1;
- перечислить из второго банка в третий сумму 3;
- перечислить из третьего банка в четвертый сумму 6.