You are given a sequence of n numbers A = (a1, a2, ..., an). At one step, you can erase any number except for the leftmost and the rightmost ones. Erasing number ai costs ai1 ai+1. Your goal is to erase all the numbers ai where 1 < i < n, in some order, such that the total cost is minimized. Give an algorithm to accomplish your goal, with O(n^3) time complexity.

When you remove a number,does ai become zero.