该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的数组 $s$，数组的每个前缀都是一个咒语

小红正在学习咒语，她了解到规则是，如果满足 $s[1…i]=s[j-i+1…j]$，那么咒语 $s[1…i]$ 必须在咒语 $s[1…j]$ 之前学习。

学习咒语 $s[1…i]$ 要支付 $a_i$ 个金币。

除此之外，她每学习一个咒语，再学习一个咒语就要价值就要增加。

假如她第 $k$ 次学习的是第 $i$ 个咒语，那么她要支付 $k*a_i$ 个金币。

她想知道她最少支付多少金币，才能把 $n$ 个咒语都学会？

输入格式

第一行一个整数 $n$

第二行数组 $s$

接下里一行 $n$ 个数字，表示 $a_1\sim a_n$。

输出格式

一个整数，表示最少需要支付金币数。 保证最终答案在 long long 范围之内。

样例

5 
1 1 2 1 1
1 2 3 4 5

50

样例说明

$s[1,1]$ 需要在 $s[1,2]$ ，$s[1,4]$ ，$s[1,5]$ 之前念

$s[1,2]$ 需要在 $s[1,5]$ 之前念

顺序如下：$s[1,3]$，$s[1,1]$，$s[1,4]$，$s[1,2]$，$s[1,5]$。

金币 $1*3+2*1+3*4+4*2+5*5=50$。

数据范围

对于 $30\%$ 的数据：$s$ 中的数组互不相同。

对于额外 $30\%$ 的数据：$1\leq n\leq 2000$，数组的循环节为 $2$。

对于 $100\%$ 的数据：$1\leq n\leq 10^5,1\leq s_i,a_i\leq 10^9$。