Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики. Тернопіль, 2016 рік.

Завдання І туру 

 А. Дивні шахи

Input file name:	chess.in
Output file name:	chess.out
Time limit:	100 ms
Memory limit:	256 M

Степан нещодавно придумав свою версію шахів, в якій гра відбувається на дошці, що має форму відмінну від традиційної.

Його дошка складається з N стовпців, i-ий з яких містить A_i клітинок. Нижні клітинки всіх стовпців утворюють один горизонтальний ряд, причому довжини стовпців впорядковані зліва направо по незростанню. На малюнку нижче наведений приклад дошки, в якій три стовпчика містять 5, 2 і 1 клітинку відповідно.

Сьогодні Степана зацікавило питання: як розставити мінімальну кількість тур на його дошці так, щоб кожну клітинку поля била хоча б одна тура. Тура б’є ті клітинки, які розташовані з нею на одній вертикалі або одній горизонталі.