You are preparing a ribbon to decorate the Christmas present box. You plan to dye the ribbon, initially white, to make a stripe pattern of different shades of red. The ribbon consists of a number of sections, each of which should be dyed as planned.
You want to prepare the ribbon with the least number of dyeing steps. Contiguous sections of the ribbon can be dyed in one step with the same shade of red. A ribbon section already dyed with some shade of red can be overdyed with dyestuff of a darker shade; it is colored with that darker shade. Overdyeing with a lighter shade is, however, not allowed. As the ribbon is initially white, all the sections must be dyed at least once.
Figure A-1: Stripe Pattern of Sample Input 1 Figure A.1 shows the pattern of Sample Input 1. The ribbon has six sections and the numbers in the sections mean the levels of shades to be dyed. Larger numbers mean darker shades. This can be made by three dyeing steps:
- dye the entire ribbon with red dyestuff of shade level 50,
- dye the second section from the left with darker shade dyestuff of level 100, and then
- dye the fifth section with dyestuff of level 100.
Write a program that computes the least number of dyeing steps to make the planned stripe pattern.
The input consists of a single test case of the following format.
| $$$n$$$ |
| $$$d_1$$$ $$$d_2$$$ $$$\cdots$$$ $$$d_n$$$ |
The test case starts with an integer $$$n$$$ $$$(1 \le n \le 100),$$$ the number of sections of the ribbon. The second line contains $$$n$$$ integers, $$$d_1, d_2, \ldots, d_n$$$, describing the planned shade levels of the $$$n$$$ sections. Here, $$$d_i$$$ means the planned shade level of the $$$i$$$-th section, which is between 1 and 100, inclusive, larger meaning darker.
Output a line containing the least number of dyeing steps to make the planned stripe pattern.
650 100 50 50 100 50
3
51 2 3 2 1
3
53 2 1 2 3
5
101 20 100 1 20 20 100 100 20 20
5
510 60 100 30 10
4
