提示: 欢迎访问OurACM平台。
Problem 1516 Binary Search Tree I

Accept: 309    Submit: 1251
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties:

  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than the node's value.
  • The right subtree of a node contains only values greater than or equal to the node's value.

Look at above, this is a a binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13.

Now, given a lot of integers, please build a binary search tree in order, Can you tell me how many leaves at last?

Input

The input will contain several test cases. Each testcase begins with an integer N(1≤n≤50000), and the second line are N disparate integers.

Output

The leaves of the tree.

Sample Input

9 8 3 1 6 4 7 10 14 13

Sample Output

4

Source

FZU 2007 ICPC Qualification Round I

Submit  Back  Status  Discuss