Sum of Pairwise Products

Interview

Time limit1sMemory limit256 MB

Summary

Given N integers, sum the products of every pair of distinct positions.

Level: Easy3 of 10
Topics: Math, Array, Prefix sum, Implementation
Solved: No attempts yet

Problem

You are given $N$ integers. Consider every way to pick two distinct positions and multiply the two integers at those positions. Print the sum of all of those products.

For example, with $N = 3$ and the integers 2, 3, 4, the ways to pick two numbers are (2, 3), (2, 4), and (3, 4), and the products are 6, 8, and 12. The total is 26.

The same value can appear more than once. Two picks at different positions count separately.

Input

The first line contains the number of integers $N$ ( $2 \le N \le 100{,}000$ ).

The second line contains $N$ integers separated by spaces. Each integer is at least $0$ and at most $10{,}000$ .

Output

Print the sum of the products over all of the picks on one line.

Examples3

Example 1
Input
```
3
2 3 4
```
Expected output
```
26
```
Example 2
Input
```
4
1 2 3 4
```
Expected output
```
35
```
Example 3
Input
```
4
2 3 2 4
```
Expected output
```
44
```