Let's say, we have a list/an array of positive integers x1, x2, ... , xn. We can do a join operation on this sequence, that means that we can replace two elements that are next to each other with one element, which is sum of these elements. For example:

-> array/list: [1;2;3;4;5;6]

• we can join 2 and 3, and replace them with 5;
• we can join 5 and 6, and replace them with 11;
• we cannot join 2 and 4;
• we cannot join 1 and 3 etc.

Main problem is to find minimum join operations for given sequence, after which this sequence will be sorted in increasing order.

Note: empty and one-element sequences are sorted in increasing order.

Basic examples:

• for [4; 6; 5; 3; 9] solution is 1 (we join 5 and 3)

• for [1; 3; 6; 5] solution is also 1 (we join 6 and 5)

What I am looking for, is an algorithm that solve this problem. It could be in pseudocode, C, C++, PHP, OCaml or similar (I mean: I woluld understand solution, if You wrote solution in one of these languages).

I would appreciate Your help.