Optimal binary search tree

Quido is experimenting with optimal binary trees. To compare their shape with the shape of perfectly or nearly perfectly balanced binary trees he introduced a special measurement of the tree: The number of nodes which have exactly one child. Obviously, the more such nodes are there in the tree the less the tree is similar to a balanced one.

     


Image 1. Optimal search tree with 19 nodes which correspond to the input of example 1 bellow. Query probabilities of particular node keys are written inside the nodes. It is not important for the solution of the problem to know the key values. There are 6 nodes with one child in this tree, they are highlighted.

The task

You are given the probability of query for each key in a binary search tree. Find the number of nodes with exactly one child in the optimal binary search tree built on these keys.

Input

The input consists of two lines. The first line contains one positive integer N ≤ 1000 representing the number of keys. The second line of input contains the list of query probabilities for all keys. The list is sorted in ascending order of the corresponding keys. Each value in the list is a positive decimal fraction less than 1.0 and with at most 7 decimal places. The values are separated by spaces. The sum of all probabilities is equal to 1. You may suppose that the probabilities define the shape of the optimal binary search tree unambiguously.

Output

The output contains one text line with one integer representing the number of nodes with exactly one child in the (unique) optimal binary search tree with input characteristics.

Example 1

Input
19
0.04 0.08 0.01 0.04 0.02 0.06 0.21 0.07 0.02 0.01 0.08 0.03 0.07 0.08 0.04 0.01 0.08 0.03 0.02
Output
6
The optimal binary search tree with input characteristics of example 1 is depicted in image 1.

Example 2

Input
5
0.1 0.2 0.4 0.2 0.1
Output
2

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set