Недавно Максу понадобилось заехать на улицу, где находятся представительства большинства деловых компаний города. Пока Макс посещал нужные ему офисы, у него появилась идея задачи.
Вдоль улицы расположены $$$N$$$ офисных зданий. В $$$i$$$-м здании $$$A_i$$$ этажей, каждый этаж целиком занимает один офис.
Сотрудники офисов часто отправляются на деловые встречи в другие офисы. На это уходит разное время:
- Если оба офиса находятся в одном здании, то сотрудникам достаточно просто подняться или спуститься на нужный этаж. Переход между этажами занимает одну единицу времени;
- Если офисы находятся в разных зданиях, то сотрудникам нужно сначала спутиться на первый этаж, выйти из здания, дойти до нужного здания, войти в него и подняться на нужный этаж. На вход или выход из здания, а также на перемещение между соседними зданиями тоже уходит одна единица времени.
Максу стало интересно, какое наибольшее время может потребоваться сотрудникам некоторого офиса, чтобы добраться до какого-то другого офиса? Помогите Максу найти ответ на этот вопрос.