Marty is trying to build a hoverboard for his engineering class. To accomplish this feat, he has decided to use electromagnetic levitation.
Marty has charged coins at his disposal. He will split a subset of his coins into pairs and, for each pair, he will place one coin on a platform and the other coin on the hoverboard. He hopes that the coins will repel each other, causing his hoverboard to rise off the platform.
Marty is hoping to impress his teacher, so he wants his hoverboard to rise as high as possible. Help Marty determine the maximum force that he can exert on the hoverboard using charged coins.
For two coins of charge and , we say the force between them is equal to the product . The force between coins that are not paired up is negligible, so we will only consider the forces between the chosen pairs of coins.
Input Specification
The first line of input contains an integer , the number of charged coins that Marty has. The next line contains integers , the charge of each coin.
Output Specification
The maximum total force that Marty can exert on the hoverboard using some pairing of coins.
Sample Input 1
4
1 2 3 4
Sample Output 1
14
Sample Input 2
5
-3 -2 1 4 5
Sample Output 2
26
Comments