Big Trace
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given the sequence $$$a_i$$$ of integers. Your task is to create the non-empty square matrix $$$B_{ij}$$$ such as:

Input

First line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the sequence $$$a$$$. $$$i$$$-th of the following $$$n$$$ lines contains one integer $$$a_i$$$ — the $$$i$$$-th member of the sequence $$$a$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Output

Print one integer — the maximum possible value of the trace.

Example

Input
6
31
10
2021
-11
0
0
Output
2052