A square pyramid of balls consists of square layers of balls stacked on top of each other. The i th (1-based indexing )layer from the top consists of exactly i2 balls. Image
You have received one such beautiful square pyramid on your birthday, with each layer having a unique color. However, being the clumsy doofus you are, you knocked it over and lost some(maybe all) balls of some(maybe all) layers. You quickly gather the balls and try to reconstruct a square pyramid(maybe of a different height) by using all the recovered balls and replacing the missing balls by new ones from the nearby shop(remember, all layers had unique colors, so you couldn't use balls from one layer in another). Find the minimum number of balls you shall have to purchase.
Input:
You are given an integer N, the number of layers having at-least one recovered ball.
Then N space separated integers follow in the next line, with A[i] representing the number of recovered balls in the ith such layer
Output:
Print the required value.
Constraints:
1 ≤ N ≤ 1,000,000
1 ≤ A[i] ≤ 1,000,000,000
For layer one, you have enough balls (1 + 0 = 1)
For layer two, you have enough balls (4 + 0 = 4)
For layer three, you buy 4 balls (5 + 4 = 9)
For layer four, you buy 14 balls (2 + 14 = 16)
For layer five, you buy 22 balls (3 + 22 = 25)
