Description

小肥同学最近在学习结构体(struct)的知识，聪明的他发现了一些小问题。在vc6.0中，一个结构体的大小并不是它的所有成员变量大小之和，这是为什么呢？好学的小肥同学到网上查阅到了一些资料：

在结构中，编译器为结构体的每个成员变量按其对界条件分配空间。各个成员变量按照它们被声明的顺序在内存中顺序存储，第一个成员变量的地址和整个结构的地址相同。在缺省情况下，C编译器为每一个成员变量按其自然对界条件分配空间。

例如，下面的结构各成员空间分配情况。

struct test {

char a;

short b;

float c;

char d;

};

结构的第一个成员a，其偏移地址为0，占据了第1个字节。第二个成员b为short类型，其起始地址必须以2字节对界（因为short是2字节）。因此，编译器在b和a之间填充了一个空字节。结构体的第三个成员c和第四个成员d恰好落在其自然对界地址上，在它们前面不需要额外的填充字节。在test结构中，成员c要求以4 字节对界，是该结构所有成员中要求的最大对界单元，因而test结构的自然对界条件为4字节，编译器在成员d后面填充了3个空字节。整个结构所占据空间为12字节。

存储结构如下：(*为填充字符，一个字母代表一个字节,如bb代表b占2个字节)

a*bbccccd***   

字节对齐的细节和编译器实现相关，但一般而言，满足三个准则：

1) 结构体变量的首地址能够被其最宽基本类型成员的大小所整除

2) 结构体每个成员变量相对于结构体首地址的偏移量都是该成员变量大小的整数倍，如有需要，编译器会在成员之间加上填充字节

3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要，编译器会在最末一个成员之后加上填充字节

小肥同学根据以上三个基本准则，顺利的解决了困挠他的小问题。那么你能不能像小肥同学一样解决这些问题呢？

Input

输入包含多组数据(<=100)。每组数据包含2行，第一行是一个正整数n(<=100)，表示该结构体有n个成员变量；第二行依次给出n个正整数，分别表示每个成员变量的大小(<=20)。

Output

对于每组数据，输出该结构体的大小。

Sample

Input

4
1 2 4 1
2
20 7

Output

12
40

Source: zxy