You and your friend are pilots in the Clone Army. You are facing the aerial fleet of the Separatist Droid Army. Droid planes move while maintaining a long line, so that their shields interact making it impossible to shoot down planes in the middle of the line. Thus, your only option is to keep shooting down planes at the edges of the line.
You and your friend have decided to make a game out of it. Each Droid plane has an importance level IMP[i]. Since the Droid planes don’t advertise their importance, both of you must follow a mixed strategy and shoot down either the first plane or the last plane with 50% chance each. If there is a single plane, the shooter with the turn will shoot it down for sure. The two of you take turns to shoot down enemy planes. You have the first turn. What is the expected sum of importance levels of planes you will shoot down?
Input/Output Specifications
Input format:
You will get two inputs:
input1 = N (1 < = N < = 1000) is the number of Droid planes
input2 = IMP (for 0 < = i < N , 1 < = IMP [i] < = 100) is an array containing the importance levels of Droid planes