A line of n signal beacons is strung out in a fixed order, each currently broadcasting an integer signal-strength reading (which may be negative, representing interference below the baseline). A field technician repeatedly performs the same repair rule: among all pairs of beacons that are currently adjacent in the line, find the pair whose two readings sum to the smallest value (if several adjacent pairs tie for the smallest sum, use whichever such pair is furthest to the left); fuse that pair into a single beacon whose reading is exactly that sum, removing the two originals and shortening the line by one beacon. The technician keeps applying this rule until the line of readings, read left to right, is non-decreasing (every beacon's reading is no smaller than the reading of the beacon immediately before it). Determine how many fusions the technician performs before that happens.
The first line contains a single integer n, the number of beacons.
The second line contains n integers, the signal-strength reading of each beacon, left to right.
Print a single integer: the number of fusions performed before the line of readings becomes non-decreasing left to right.
Example 1
Input
5 5 2 3 9 3
Expected
3
Explanation
Readings are 5, 2, 3, 9, 3. Adjacent sums are 5+2=7, 2+3=5, 3+9=12, 9+3=12; the smallest is 5, so beacons 2 and 3 fuse into a reading of 5, giving 5, 5, 9, 3 (not yet non-decreasing). Adjacent sums are now 5+5=10, 5+9=14, 9+3=12; the smallest is 10, so the first two fuse into 10, giving 10, 9, 3 (still not non-decreasing). Adjacent sums are now 10+9=19, 9+3=12; the smallest is 12, so the last two fuse into 12, giving 10, 12, which is non-decreasing. Three fusions were performed.
Example 2
Input
4 1 2 2 1
Expected
2
Explanation
Readings are 1, 2, 2, 1. Adjacent sums are 1+2=3, 2+2=4, 2+1=3; the leftmost and rightmost pairs tie at 3, so the leftmost is chosen: beacons 1 and 2 fuse into 3, giving 3, 2, 1 (not non-decreasing). Adjacent sums are now 3+2=5, 2+1=3; the smallest is 3, so the last two fuse into 3, giving 3, 3, which is non-decreasing. Two fusions were performed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →