Program and explain algorithm

Remember that when a problem asks you to design an algorithm, you must also prove the algorithms correctness and analyze its running time, i.e., the running time must be bounded by a polynomial function of the input size.

(1) (10 points) One day while resting under an apple tree, Anand figured out how to perfectly toss a ring onto any peg in the first attempt. Anand goes to Apple Fest to show off their newfound skill. Anand won a raffle and earned the right to play a lucrative new version of the ring toss. Here, you are given n rings and n pegs with radii r1,,rn, are kept in that order from left to right. Every time a ring is tossed correctly onto a peg, that peg along with the ring is completely removed. If you toss correctly onto peg j and it has left neighbor peg i and right neighbor peg k, then you get rirjrk dollars. If j does not have a left neighbor and has a right neighbor or j does not have a right neighbor and has a left neighbor, then you get rjrk dollars and rirj dollars respectively. If j is the only peg left, then you get rj dollars. Anand needs your help to figure out what is the maximum amount of money they can make from this game. The input format (passed via stdin, terminated by a newline) is as follows: - One line containing one positive integer: n, the number of pegs. - One line containing n positive integers, the radii ri of each peg for 1in. Your program should output, to stdout, 1 line: - The first line should contain the maximum amount of money Anand can make from this game. - Your output should be terminated by a newline. Here are some input bounds: - 1n250