C. Potions Homework
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Harry Water, Ronaldo, Her-my-oh-knee and their friends have started a new school year at their MDCS School of Speechcraft and Misery. At the time, they are very happy to have seen each other after a long time. The sun is shining, birds are singing, flowers are blooming, and their Potions class teacher, professor Snipe is sulky as usual. Due to his angst fueled by disappointment in his own life, he has given them a lot of homework in Potions class.

Each of the n students has been assigned a single task. Some students do certain tasks faster than others. Thus, they want to redistribute the tasks so that each student still does exactly one task, and that all tasks are finished. Each student has their own laziness level, and each task has its own difficulty level. Professor Snipe is trying hard to improve their work ethics, so each student’s laziness level is equal to their task’s difficulty level. Both sets of values are given by the sequence a, where ai represents both the laziness level of the i-th student and the difficulty of his task.

The time a student needs to finish a task is equal to the product of their laziness level and the task’s difficulty. They are wondering, what is the minimum possible total time they must spend to finish all tasks if they distribute them in the optimal way. Each person should receive one task and each task should be given to one person. Print the answer modulo 10 007.

Input

The first line of input contains integer n (1 ≤ n ≤ 100 000) — the number of tasks. The next n lines contain exactly one integer number ai (1 ≤ ai ≤ 100 000) — both the difficulty of the initial task and the laziness of the i-th students.

Output

Print the minimum total time to finish all tasks modulo 10 007.

Example
Input 
2
1
3
Output 
6
Note

In the first sample, if the students switch their tasks, they will be able to finish them in 3 + 3 = 6 time units.


思路：

题意就是，给你n个数，每个数用两次，让你求n个数相乘的和的最小值。就比如，1 2 3 4 5，就让你用这5个数，每个数只能用两次，然后求他们的乘积的和，那么就是5*1+4*2+3*3+2*4+1*5。我的想法就是，逆序相乘，最大的×最小的，最小的×最大的这样，但是一开始WA了八次。。WA的地方就在于数据大小会把int爆掉。一开始是两个数乘完再取模，WA了。。大题估算了一下乘积最多在10的10次方，以为不会爆。事后才知道原来int数最大大约到10的9次方。也算是涨姿势了，以后对int类型数据的大小判断的时候就知道点东西了...


代码：

[cpp]  view plain  copy
  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstdlib>  
  4. #include<cstring>  
  5. #include<algorithm>  
  6. #define inf 10007  
  7. using namespace std;  
  8.   
  9. int a[100000+5];  
  10.   
  11. int main()  
  12. {  
  13.     //freopen("in.txt","r",stdin);  
  14.     int n;  
  15.     while(scanf("%d",&n)!=EOF)  
  16.     {  
  17.         for(int i=0;i<n;i++)  
  18.         {  
  19.             scanf("%d",&a[i]);  
  20.         }  
  21.         sort(a,a+n);  
  22.         long long sum=0;  
  23.         for(int i=0;i<n;i++)  
  24.         {  
  25.             sum=(sum+a[i]%inf*a[n-i-1]%inf)%inf;  
  26.         }  
  27.         printf("%lld\n",sum);  
  28.     }  
  29. }