Hi everybody !

I've learn to use Fenwick Tree for a long time but recently I perceive I didn't use it optimally.

So I have some question about Fenwick Tree, I need your help :

1, Can we use Fenwick Tree for min-max query for an inteval array;

2, Can we use it as a Dynamic Fenwick Tree with number of nodes not exeed 1e9 and how to.

3, Can we one Fenwick Tree for two usages: sum and min or sum and max.

They maybe fool questions, please help me if you can !!

Sorry because of my poor English !!

Can somebody please explain how dynamic binary index trees work and give me an implementation, I would appreciate your help!

I meet some dificult in coding it !

Sorry about my pour English !

Thanks in advance! :)

Link of the problem :http://www.spoj.com/problems/TOINCSEQ/

In short: You are given a sequence of non-negative integers a1, a2, …, an. You are allowed to perform some operators on the sequence. Each operator consists of 2 steps: choosing an arbitrary value, then increasing (or decreasing) all elements of the selected value in the current sequence by 1.

For example, the sequence 1 9 9 2 2 will become 1 9 9 3 3 if you decide to increase all elements of value 2.

What is the minimum number of operators does it take to make the given sequence a non-decreasing sequence?

Input

The first line consits of an integer N, the number of elements in the sequence. The second line consists of N elements of the sequence. Output

The mininum number of operators needed to make the sequence non-decreasing. Example

Input: 5

1 9 9 2 2

Output: 7 Constraints

1 ≤ N ≤ 10^5. Each element of the sequence is a non-negative integer not exceeding 10^9. ***************************************************************************

I think we can uses DP but I had no idea then.

Help me please !!!