题目描述

有一种由 $n$ 种英雄组成的卡牌，英雄编号从 $1$ 到 $n$，小马楼在班级收集这 $n$ 种英雄卡，同学们发挥友谊的精神纷纷赞助他，第 $i$ 种英雄收集了 $A_i$ 张。

有了这些卡片后他突发奇想，如果把这些卡牌固定排成一个序列，这个序列中包含尽可能多长度为 $n$ 且含所有英雄的子串（如1 2 3 4 1 2 3这个序列包含1-4的子串有1 2 3 4，2 3 4 1，3 4 1 2，4 1 2 3）， 除了同学赞助的卡牌外，小马楼还有10个硬币，每个硬币可以去商店兑换一张任意编号的英雄卡，现在他想知道，兑换完英雄卡后，他排的序列最多能得到多少组包含所有英雄的子串。

输入格式

第一行 一个整数 $n$，表示卡牌的种类

第二行 $n$ 个整数 $A_i$，表示每种卡牌从同学那得到的数量

输出格式

一个整数 表示最多包含所有英雄的子串数量

如果不能组成，输出-1

输入样例1

2
1 1

输出样例1

11

输入样例2

10
1 3 1 2 1 9 3 5 7 5

输出样例2

28

样例解释#1

将10枚硬币买入1号5张，2号5张，组成的排列为【1 2 1 2 1 2 1 2 1 2 1 2】

组成的子串1 2有6组，组成的2 1子串有5组，共11组

数据范围

对于30%的数据 $1 \le n \le 100,1 \le a_i \le 1000 , 所有a_i相等$

对于100%的数据 $1 \le n \le 10^6 ,0\le a_i \le 1000$

备注：本题测试数据为民间数据