T267927 「GOI-R1」和璞鸢

$$\pmb{\color{CadetBlue}『金鹏者，号“金翅鹏王”，又名“降魔大圣”。不知其始，不知其终。』}$$ $$\pmb{\color{CadetBlue}『唯春夜灯祭，望浮光于孤云阁上，璃月民曰：“此护法夜叉讨魔也。”』}$$ $$\pmb{\color{CadetBlue}『或闻笛音出于荻洲，寻之不见其人，曰：“是夜叉唤旧友归矣。”』}$$ --- $$\pmb{\color{CadetBlue}如遇失道旷野之难，路遭贼人之难}$$ $$\pmb{\color{CadetBlue}水火刀兵之难，鬼神药毒之难}$$ $$\pmb{\color{CadetBlue}恶兽毒虫之难，冤家恶人之难}$$ $$\pmb{\color{CadetBlue}便呼我名}$$ $$\pmb{\color{CadetBlue}『三眼五显仙人』『魈』，听召，前来守护}$$

魈真君加入你的队伍后，因为吃了太多杏仁豆腐，导致行动迟钝，在和丘丘人战斗的过程中他的和璞鸢磨损了，为此，你需要负起责任，帮魈真君买到修补和璞鸢的材料。 你来到了常去的一家商铺，由于你是老顾客，所以老板拿出了他商铺里 ~~最好~~ 最贵的矿石，开价 $998244353$ 摩拉。但是你没有钱，而且怀疑老板的人品，于是你找到了钟离先生和达达利亚。作为璃月城最精通玉石的人，钟离先生把这块长条形的矿石分成了 $n$ 段，并给每一段都标上了一个价值，形成了一个序列 $A$。同时，钟离先生告诉你，和璞鸢是极为特殊的武器，所以对于一段区间 $[l,r]$ 上的材料，当且仅当其对应序列 $A$ 中 $[l,r]$ 上的子序列是一个 **『周期子序列』** 时，这段区间上的材料才能够被用作修复和璞鸢。 由于~~愚人众执行官第十一席~~至冬国最大的玩具推销员达达利亚有着雄厚的资金，你决定买下价值最大的一段矿石。所以，你首先需要知道其最大价值是多少。 对 **『周期子序列』** 的定义是：对于一个序列 $A$，若对于序列 $A$ 中区间 $[l,r]$ 上的子序列，在序列 $A$ 中存在区间 $[l',r']$ 满足 $l' \not = l,r'\not = r$ 并且区间 $[l',r']$ 上的子序列与区间 $[l,r]$ 上的子序列完全相等，则称区间 $[l,r]$ 的子序列是一个周期子序列。如 $A = \{1,2,1,2,1,3\}$ 时，$\{1,2\}$ 和 $\{1,2,1\}$ 均是符合条件的周期子序列，而 $\{1,2,1,3\}$ 则不是。 对一个周期子序列的 **『价值』** 的定义是：对于一个周期子序列 $[l,r]$，若其子序列和为 $s$，出现次数为 $k$，则其价值为 $s \times k$。 --- #### 形式化题意 给定一个有 $n$ 个元素的数列，求其中价值最大的周期子序列，并输出其最大价值。其中关于 **『周期子序列』** 和其 **『价值』** 的定义如上。

第一行一个正整数 $n$，这块矿石被分成了 $n$ 段。 第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 100$)，第 $i$ 个数字表示钟离先生给第 $i$ 段矿石标上的价值。

一个整数 `x`，表示该你能够买到的符合条件的材料的最大价值。若不存在则输出 `-1`。

------------ ### 样例解释 `1 2 1` 为一个周期子序列，分别在 $[1,3]$，$[3,5]$ 上各出现一次，共出现两次，价值为 $(1+2+1)\times 2=8$，显然不存在价值更大的周期子序列。 ---- ### 数据范围 **本题采用捆绑测试。** | Subtask | $n \leq$ | 分数 | | :----------: | :----------: | :----------: | | 1 | $100$ | $10$ | | 2 | $5000$ | $30$ | | 3 | $10^6$ | $60$ |