E. Разноцветные шары
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На столе стоят n коробок с разноцветными шарами. Цвета пронумерованы от 1 до n. В i-й коробке лежит ai шаров i-го цвета. Требуется разбить шары на минимальное количество наборов таких, что:

  • каждый шар принадлежит ровно одному набору,
  • каждому набору принадлежит хотя бы один шар,
  • в каждом наборе все шары одного цвета,
  • размеры любых двух наборов отличаются не более чем на 1.

Выведите искомое минимальное количество наборов.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 500).

Во второй строке задано n целых чисел a1, a2, ... , an (1 ≤ ai ≤ 109).

Выходные данные

Выведите одно число — минимальное возможное количество наборов.

Примеры
Входные данные
3
4 7 8
Выходные данные
5
Входные данные
2
2 7
Выходные данные
4
Примечание

В первом примере можно разбить шары на следующие наборы: первую коробку — на набор из 4 шаров, вторую — на наборы из 3 и 4 шаров и третью — на два набора из 4 шаров.