Hi guys. Let's discuss this problem:

An array is good if the maximum element is no longer than the length.

The cost of the array is the length squared.

Divide the given array into several disjoint continuous parts so that each part is good and the total cost of all parts is the lowest possible.

Input In the first line, the positive integer n (1≤n≤100000) — the size of the array.

The next line contains n integers a1,a2,…,an(1≤ai≤n) Output Print the minimum possible total cost of all parts.