Задача Затопление (flooding).
Герой известного мультсериала Колыван решил построить себе бассейн. Поскольку он очень скуп, он пытается использовать уже имеющееся строение. Строение представляет собой абсолютно ровный коридор единичной ширины, в котором имеется N перегородок. Если расположить ось Х вдоль коридора, все перегородки будут находиться точно в ее целочисленных координатах с шагом 1, причем по ширине перегородки занимают весь коридор, а высоты могут отличаться. Создаваемый бассейн должен иметь максимально большой возможный объем при условии, что из всех имеющихся перегородок нужно оставить только две и увеличивать их высоту запрещено. Формат ввода/вывода. Программа flooding считывает с клавиатуры (стандартного устройства ввода) целое число N (2<=N<=105) – количество перегородок. Затем считывается N целых чисел аi (1<=аi<=109) – высоты перегородок. Программа flooding выводит на экран (стандартное устройство вывода) единственное число – максимальный объем создаваемого бассейна при описанных ограничениях. Пример входных и выходных данных.
|