Alternate sum of a nonempty set is the result of operations described as follow: Firstly, all the elements of arranged in
non-increasing sequence. Secondly, alternate sum could be obtained by the following formula:

Where:
and
For example, and so alternate sum of is 2. It?s very easy for you to
compute the alternate sum, isn?t it? But can you tell me the total value of all the subsets? alternate sum in set ?

输入格式

There are several test cases. For each test case, it contains:
Line 1: One integer N (1<=N<=1000) which specifies the size of set
Line 2: N integers (you are ensured that the absolute value of each integer is less than ) which specify the elements of set .
There is a blank between two consecutive integers.
The input will be ended by zero.

输出格式

The answer of the total value may be very large, so you should divide this answer by 2006 and just output the remainder instead.

样例输入

1
-1
2
0 4
3
1 3 2
0

样例输出

2005
8
12

#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i,answer,max;
int setN[1000];
while(scanf("%d",&n),n)
{
   for(i=0;i<n;i++)
   scanf("%d",&setN[i]);
   max=setN[0];
   for(i=1;i<n;i++)
    if(setN[i]>max)
     max=setN[i];
   answer=max;
   for(i=1;i<n;i++)
   {
    answer*=2;
    if(answer<0)//防止负数越界
     answer+=2006;
    answer%=2006;
   }
   if(answer<0)
    answer+=2006;
   printf("%d\n",answer%2006);
  
}
return 0;
}