A dragon was there behind the mountain having power 'P' initially and his power is associated with each stone of mountain.↵
If stone of ith position is broken by hammering, then power of dragon will decrease by an amount equal to hardness[i]^hardness[i-1]^hardness[i+1]) where ab = a raised to the power of b
↵
After ith stone is broken, we re-label the positioning of stones by decreasing N by 1 i.e. [0,N-1] from left to right.You can break the stone in any order.Power required to break stone of hardness value say h is 'h' units itself.First and last stone are not allowed to break otherwise dragon will come and attack Thorin.↵
↵
Find the minimum power required to kill the dragon and break the mountain. Breaking the stones is hence added to the the final power. Help Thorin !!↵
↵
Input: ↵
Given an integer N number of stones and an integer 'P' power of dragon initially.↵
Next line contains N values corresponding to hardness of the stones.↵
↵
Ouput:↵
Output the minimum power required to kill the dragon and break the mountain.↵
↵
Constraints:↵
↵
1 <= N <= 500↵
1 <= P <= 10^18 ↵
1 <= hardness value <= 3↵
Sample Input(Plaintext Link)↵
4 7000↵
1 2 3 3↵
Sample Output
442↵
Explanation↵
Break the 3rd stone => 3^(2^3) = 6561 ↵
Now, stones left => 1,2,3↵
Break the 2nd stone => 2^(1^3) = 2↵
Power of dragon decrease by 6561 + 2 = 6563↵
Remaining power of dragon = 7000 — 6563 = 437↵
Power spent in breaking stones = 2+3 = 5↵
So , Power required to kill the dragon = 437+5 = 442
