В Берляндии оппозиционеры собираются устроить массовые гуляния по бульвару. Бульвар состоит из n расположенных в ряд плиток, пронумерованных от 1 до n cправа налево. Прогулка оппозиционеров должна начаться на плитке номер 1 и закончиться на плитке номер n. В ходе прогулки разрешается перемещаться справа налево между соседними в ряду плитками, а также перепрыгивать через одну плитку. Более формально, с плитки номер i (i < n - 1) можно попасть на плитку номер i + 1 или на плитку номер i + 2 (с плитки номер n - 1 можно попасть только на плитку номер n). Можно считать, что все перемещения оппозиционеров происходят мгновенно.

Для того, чтобы сорвать оппозиционную акцию, берляндский кровавый режим организовал дождь. Плитки на бульваре плохого качества и они быстро разрушаются под дождем. Известно, что i-тая плитка приходит в негодность после a_i дней дождя (в день a_i плитка еще не разрушена, а в день a_i + 1 уже разрушена). Конечно же, никому не разрешается ходить по разрушенным плиткам! Поэтому прогулка оппозиционеров считается сорванной, если либо разрушена плитка номер 1, либо разрушена плитка номер n, либо невозможно дойти с плитки номер 1 до плитки номер n, двигаясь по неразрушенным плиткам.

Оппозиционеры хотят собрать побольше единомышленников для своей прогулки. Поэтому чем больше времени у них есть на сборы, тем лучше. Помогите оппозиционерам узнать, сколько у них еще осталось времени, и скажите, в течение скольких дней прогулка с плитки номер 1 на плитку номер n будет возможной.