Беси придумала новую игру:
Игрок стреляет коровой по одномерной сцене состоящей из множества стогов с сеном
расположенных в различных точках на числовой прямой. Корова приземляется на стог
с силой достаточной чтобы взорвать стог, что вызовет цепную реакцию взрывов
близлежащих стогов. Цель игры - использовать одну корову в начале игры так,
чтобы сдетонировало как можно больше стогов.
\(N\) стогов сена расположены в различных целочисленных позициях
\(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлилась в позицию \(x\),
этот стог взрывается с радиусом взрыва 1, что означает, что стоги сена, которые
находятся на расстоянии 1 от этого стога, тоже взрываются - одновременно, но уже
с радиусом взрыва, равным 2. На следующем шагу взрываются все в радиусе взрыва,
но новые взрывы будут уже с радиусом 3. В общем случае, в момент времени \(t\)
взрывается некоторое количество коров и каждый взрыв имеет радиус \(t\). Эти взрывы
инициируют взрывы коров попавших в зону поражения в момент времени \(t+1\) с
радиусами взрывов \(t+1\) и т.д
Пожалуйста, определите максимальное количество стогов сена, которые могут
быть взорваны, если первую корову приземлить оптимальным образом для начала
цепной реакции.
ФОРМАТ ВВОДА (файл angry.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100\)). Оставшиеся \(N\)
строк все содержат целые числа \(x_1 \ldots x_N\) (каждое в диапазоне
\(0 \ldots 1,000,000,000\)).)
ФОРМАТ ВЫВОДА (файл angry.out):
Пожалуйста, выведите максимальное количество стогов сена, которое
одна корова может вынудить взорваться.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
8
5
6
13
3
4
|
5
|