Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Heap
Time Limit: 5000MSMemory Limit: 131072K
Total Submissions: 3325Accepted: 759

Description

A (binary) heap is an array that can be viewed as a nearly complete binary tree. In this problem, we are talking about max-heaps.

A max-heap holds the property that for each node than the root, it’s key is no greater than its parent’s. Upon this we further require that for every node that has two children, key of any node in the subtree rooted at its left child should be less than that of any node in the subtree rooted at its right child.

Any array can be transformed into a max-heap satisfying the above requirement by modifying some of its keys. Your task is find the minimum number of keys that have to be modified.

Input

The input contains a single test case. The test case consists of nonnegative integers distributed on multiple lines. The first integer is the height of the heap. It will be at least 1 and at most 20. Then follow the elements of the array to be transformed into a heap described above, which do not exceed 109. Modified elements should remain integral though not necessarily nonnegative.

Output

Output only the minimum number of elements (or keys) that have to be modified.

Sample Input

3
1
3 6
1 4 3 8

Sample Output

4

Hint

   1                 10
/ \ / \
3 6 =====> 3 9
/ \ / \ / \ / \
1 4 3 8 1 2 4 8

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator