Maximum Sum Path :
Difficulty Level : Easy
Submissions : 318
Asked In :
Marks :10
: 3 | : 0
You are given an array A of length N consisting of distinct elements.
You need to construct a Binary Search Tree(BST) by inserting each element one by one from array A, starting from the first element till last.
Determine the maximum path sum from root node to leaf node of the BST after each new element is inserted.
Input
First line contains a single integer n (size of array or number of nodes) such that ($$$1 \le n \le 20000$$$).
Second line contains n space separated distinct integers $$$A_i$$$ where ($$$ 1 \le A_i \le 20000$$$).
Output
Print the maximum path sum from root node to leaf node of the BST.
Examples
Input
3 1 2 3
Output
6
Input
6 40 80 20 50 60 70
Output
300
