Mimi decides to play a game with the following rules:
A -subarray is a subarray of length .
The -uteness of an array is defined as the sum of the sum of all -subarrays of .
The winner is the person who can output the -uteness of for , where is the number of elements in . Can you beat Mimi?
For all subtasks, .
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
The first line of input will contain a single integer, .
The next line of input will contain space separated integers, .
lines, with the line being the -uteness of the array.
5 1 1 1 1 1
5 8 9 8 5