Задача №114699. Украшение дома
Даня играет со своими друзьями в известную игру minecart. На своем сервере он построил дом, передняя стена которого состоит из \(n\) столбиков квадратных блоков, \(i\)-й столбик имеет высоту \(h_i\).
Недавно в игре вышло обновление, в котором в игру были добавлены прямоугольные картины. Теперь Даня хочет выбрать некоторую картину и украсить картинами такого размера переднюю сторону дома так, чтобы каждый блок стены был покрыт хотя бы одной картиной. Картины можно поворачивать на \(90\) градусов, накладывать друг на друга, но нельзя, чтобы под каким-то блоком картины не было блока стены.
Даня считает, что красота картины равна её площади. Помогите Дане найти картину максимальной красоты, такую что её копиями и поворотами можно украсить всю переднюю стену дома.
В первой строке содержится одно целое число \(n\) \((1 \leq n \leq 200\,000)\) — количество столбиков на передней стене дома.
Во второй строке содержатся \(n\) целых чисел \(h_1, h_2, \ldots, h_n\) \((0 \leq h_i \leq 10^9)\) — высоты столбиков.
Гарантируется, что хотя бы один столбик имеет высоту больше 0.
Выведите максимальную площадь картины, такую что такими картинами и её поворотами Даня сможет украсить всю переднюю стену дома.
В первом примере подойдёт картина длиной \(1\) и высотой \(4\).
Во втором примере подойдёт картина длиной \(2\) и высотой \(4\).
В третьем примере подойдёт картина длиной \(3\) и высотой \(5\).
Можно показать, что нельзя покрыть заборы прямоугольниками большей площади.
На рисунках ниже показаны примеры покрытия картинами стены в первом и втором примерах:
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(h_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 11 | \(n \leq 10\) | \(h_i \leq 10\) | 0 | |
| 2 | 12 | \(n \leq 500\) | \(h_i \leq 500\) | 0, 1 | |
| 3 | 18 | \(n \leq 5000\) | \(h_i \leq 5000\) | 0, 1, 2 | |
| 4 | 16 | \(n \leq 5000\) | – | 0–3 | |
| 5 | 18 | – | \(h_i \leq 500\) | 0, 1, 2 | |
| 6 | 25 | – | – | 0–5 | |
5 4 4 1 4 4
4
7 2 4 4 2 0 4 4
8
6 3 6 6 6 5 4
15