题目描述

一栋别墅有 \(n\) 层，著名的小偷 Peer Brelstet 发现，在最顶层有一个画室，里面珍藏着珍贵的画。Peer Brelstet 决定，从外面扔一个绳索，自己从外面爬进去。但每层的高度不同，所以 Peer Brelstet 爬的时间也不同（可以认为是楼层高度）。Peer Brelstet 有绝门功夫，可以让他一下子爬两层或一层，而且不耗费时间。但这样会大大消耗 Peer Brelstet 的体力，所以在使用完绝门功夫后必须老老实实爬上一层后再使用绝门功夫。你是他的同伙，现在 Peer Brelstet 想问你他究竟要多长时间才能爬到顶层。当然，他希望时间越短越好。

格式

输入格式

第一行一个数 \(n (n<=1000000)\),表示别墅的层数.

第二行 \(n\) 个数 \((<=100)\),表示从下往上每层的高度.

输出格式

一个数,表示最短时间.

样例1

样例输入1

6
5 2 4 5 3 2

样例输出1

5