Миллионер Билл подал в мэрию прекрасного курортного города заявку на покупку участка на побережье. Администрация города согласилась выделить миллионеру участок, но выставила требование: в целях соблюдения принципов городского планирования участок обязательно должен быть прямоугольной формы и одна из его сторон должна быть параллельна гряде гор, идущих вдоль побережья. Побережье представляет собой последовательность прямоугольных полос ширины один метр, одна из метровых сторон которых упирается в гряду гор, представляющую собой прямую линию. Полосы касаются друг друга боковыми сторонами. Море находится с противоположной от гор стороны полос (см. рисунок). Помогите Биллу выбрать участок максимальной площади, удовлетворяющий требованиям мэрии.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
В первой строке входного файла записаны два числа: $$$n$$$ — длина берега в метрах ($$$1 \leq n \leq 10^5$$$) и $$$t$$$ — номер подзадачи. В следующей строке записаны через пробел $$$n$$$ целых неотрицательных чисел $$$h_i,\, i = 1,..,n$$$, не превосходящих $$$10^9$$$ – последовательные длины всех полос в метрах. Номер подзадачи $$$t$$$ определяет дополнительные ограничения на вид входных данных (см. описание системы оценивания ниже).
В выходной файл требуется вывести единственное число — максимальную площадь участка.
Решение задачи оценивается независимо на каждом тесте. За каждый успешно пройденный тест, кроме тестов из условия, начисляется 2 балла. Прохождение тестов из условия является необходимым условием для оценивания задачи на остальных тестах. Остальные тесты оцениваются независимо друг от друга. Тесты разбиты на следующие группы тестов, соответствующие номеру подзадачи $$$t$$$ во входных данных задачи:
| Номер подзадачи | Описание | Тесты в группе | Балл за группу |
| 0 | Тесты из условия | 1 – 2 | 0 |
| 1 | Дополнительное ограничение: $$$n \leq 1000$$$ | 3 – 7 | 10 |
| 2 | Дополнительное ограничение: последовательность длин полос является монотонно неубывающей, то есть для каждого $$$i = 1, ..., n - 1$$$ выполнено: $$$h_i \leq h_{i+1}$$$ | 8 – 12 | 10 |
| 3 | Дополнительное ограничение: побережье имеет форму бухты, то есть существует некоторое $$$j$$$, такое что $$$1 \leq j \leq n$$$ и $$$h_i \geq h_{i+1}$$$ для всех $$$i = 1, .., j-1$$$ и $$$h_i \leq h_{i+1}$$$ для всех $$$i = j, ..., n$$$ | 13 – 17 | 10 |
| 4 | Дополнительное ограничение: побережье имеет форму мыса, то есть существует некоторое $$$j$$$, такое что $$$1 \leq j \leq n$$$ и $$$h_i \leq h_{i+1}$$$ для всех $$$i = 1, .., j-1$$$ и $$$h_i \geq h_{i+1}$$$ для всех $$$i = j, ..., n$$$ | 18 – 22 | 10 |
| 5 | Дополнительное ограничение: $$$h_i \leq 100$$$ для всех $$$i = 1, ..., n$$$ | 23 – 27 | 10 |
| 6 | Без дополнительных ограничений | 28 – 52 | 50 |
5 0 3 4 5 4 2
12
8 0 6 7 3 4 6 8 3 5
24
