Vadim’s home renovation is almost complete, and he only has to fully drive in N nails into one board. These nails are arranged in a single row, numbered from 1 to N, with the i-th nail being not driven in by l_i centimeters. Vadim has a hammer at his disposal. This hammer can hit two nails at a time, meaning one strike will always be over one pair of neighboring nails. If one nail in the pair is driven in less, it will be driven in by 1 cm. If both nails are equally not driven in, both will be driven in by 1 cm. The renovation needs to be finished as quickly as possible since Vadim is hosting a party at home in the evening. Help him find the minimum number of strikes required to drive in all the nails.

The first line contains an integer N — the number of nails in the board (2 ≤ N ≤ 10⁵).

The second line contains N integers l_i — the number of centimeters that the i-th nail is not driven in (1 ≤ l_i ≤ 10⁹).

Output the minimum number of strikes required to drive in all the nails.