NPC2014B - House Fence

"Holiday is coming, holiday is coming, hurray hurray!" shouts Joke in the last day of his college. On this holiday, Joke plans to go to his grandmother's house located in Schematics village. Joke's grandmother's house is more than a hundred years old. Joke is very kind hearted, so he wants to help renovate the house by painting the fence. The fence consists of N vertical boards placed on a line. The boards are numbered 1 to N from left to right, and each of them has the length of 1 meter and the height of Ai meters.

Joke's grandmother has a paintbrush that can be used to paint the fence. That paintbrush has a length of 1 meter. Joke paints the fence by brushing either horizontally or vertically, but the paint is expensive so Joke wants to minimize the number of paintbrush stroke. On each stroke, the paintbrush will make either a horizontal or vertical line. Also, the paintbrush must be touching the fence for the entire duration of the stroke. Joke also does not want to paint previously panted segment before. Help Joke to find the minimum number of stroke until the entire fence is covered with paint.

Input

First line contains a number N, the number of boards on the fence. The second line contains N numbers, A1, A2, A3 ... An representing the height of each board.

Output

Minimum number of stroke to paint the entire fence.

Examples

Input 1:
5
2 2 1 2 1

Output 1:
3
Input 2:
2
2 2

Output 2:
2
Input 3:
1
5

Output 3:
1

Explanation

  • On the first example, first stroke is done horizontally on the lowest segment. Second stroke is done horizontally on board 1 and board 2 on 2 meters height. Third and last stroke is done on board 4 on 2 meters height, doesn't matter horizontally or vertically.
  • On the second example, Joke can do either 2 horizontal strokes or 2 vertical strokes.
  • On the third example, only 1 vertical stroke is needed.

Constraints

  • 1 ≤ N ≤ 5000
  • 1 ≤ Ai ≤ 1000000000

Added by:Andy
Date:2014-10-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NPC Schematics 2014

hide comments
2016-06-02 10:28:47 Sushovan Sen
Can you check Id: 17033391.
2015-04-02 20:35:06 sathya_dev
Always failed at 26th test case.. Any special case there?
2014-11-05 10:34:24 Andy
@anurag your logic
2014-11-03 16:26:24 anurag garg
@author can you have a look at my submission 12803576 and tell me whats wrong with it
thanks
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.