Переберем столб, в котором в итоге будет минимальная глубина. Сделаем двоичный поиск по глубине, которая будет в итоге в этом столбе. Пусть мы выбрали столб $$$x$$$ и глубину $$$h$$$. Нужно посчитать, какое минимальное количество минут потребуется, чтобы у столба $$$x$$$ стала высота $$$h$$$. Чтобы $$$x$$$-ый столбец мог иметь высоту $$$h$$$, его соседи должны иметь высоту не более $$$h + 1$$$, их соседи должны иметь высоту не более $$$h + 2$$$ и так далее. Найдем ближайший слева столбец $$$i$$$, что $$$h_i \le h + (x - i)$$$. Заметим, что для всех $$$j \le i$$$ верно, что $$$h_j \le h + (x - j)$$$, а для всех $$$i < j \le x$$$ верно $$$h_j > h + (x - j)$$$. Значит, столбы левее $$$j$$$-го уменьшать не нужно, а правее — нужно. Аналогично справа от $$$x$$$. Значит, чтобы найти количество минут, которое потребуется, чтобы выкопать столб $$$x$$$ до высоты $$$h$$$, можно сложить высоты на отрезке, и вычесть сумму двух арифметических прогрессий. Границы отрезка также можно найти двоичным поиском.