# E. Simple Skewness

time limit per test:3 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Define the simple skewness of a collection of numbers to be the collection's mean minus its median. You are given a list of n (not necessarily distinct) integers. Find the non-empty subset (with repetition) with the maximum simple skewness.

The mean of a collection is the average of its elements. The median of a collection is its middle element when all of its elements are sorted, or the average of its two middle elements if it has even size.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in the list.

The second line contains n integers xi (0 ≤ xi ≤ 1 000 000) — the ith element of the list.

Output

In the first line, print a single integer k — the size of the subset.

In the second line, print k integers — the elements of the subset in any order.

If there are multiple optimal subsets, print any.

Examples

Input

```4
1 2 3 12```

Output

```3
1 2 12 ```

Input

```4
1 1 2 2```

Output

```3
1 1 2 ```

Input

```2
1 2```

Output

```2
1 2```

Note

In the first case, the optimal subset is

, which has mean 5, median 2, and simple skewness of 5 - 2 = 3.

In the second case, the optimal subset is

. Note that repetition is allowed.

In the last case, any subset has the same median and mean, so all have simple skewness of 0.

## 分析

1.最大偏度一定≥0

2.最大偏度子集必定有元素个数为奇数个的。

3.平均值先递增后递减

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N=200020;
6 {
7     int x=0,f=1;
8     char ch=getchar();
9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-')
12             f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16     {
17         x=x*10+ch-'0';
18         ch=getchar();
19     }
20     return x*f;
21 }
22 int n;
23 ll s[N<<1],a[N<<1];
24 int ansi=1,ansp;
25 double ans;
26 //最大偏度≥0，所以初始值就是只有第一个元素，偏度为0
27 ll sum(int i,int j)
28 {
29     return s[n]-s[n-j]+s[i]-s[i-j-1];
30 }
31 int main()
32 {
34     for(int i=1;i<=n;i++)
35         cin>>a[i];
36     sort(a+1,a+1+n);
37     for(int i=1;i<=n;i++)
38     {
39         s[i]=s[i-1]+a[i];
40     }
41     for(int i=2;i<n;i++)
42     {
43         int l=1,r=min(i-1,n-i),m;
44         ll s1,s2;
45         while(l<r)
46         {
47             int mid=(l+r)/2;
48             s1=sum(i,mid)*(2*mid+3);
49             s2=sum(i,mid+1)*(2*mid+1);
50             if(s1>s2)
51             {
52                 r=mid;
53             }
54             else
55             {
56                 l=mid+1;
57                 if(s1==s2)
58                     break;
59             }
60         }
61         if(1.0*sum(i,l)/(2*l+1)-a[i]>ans)
62         {
63             ans=1.0*sum(i,l)/(2*l+1)-a[i];
64             ansi=i;
65             ansp=l;
66         }
67     }
68     cout<<ansp*2+1<<endl;
69     cout<<a[ansi]<<" ";
70     for(int i=1;i<=ansp;i++)
71     {
72         cout<<a[ansi-i]<<" "<<a[n-i+1]<<" ";
73     }
74     cout<<endl;
75     return 0;
76 }```

0 条评论

• ### Codeforces 833D Red-black Cobweb【树分治】

D. Red-black Cobweb time limit per test：6 seconds memory limit per test：256 mega...

• ### AIM Tech Round 4 (Div. 2)(A，暴力，B，组合数，C，STL+排序)

A. Diversity time limit per test：1 second memory limit per test：256 megabytes in...

• ### POJ 3154 Graveyard【多解，数论，贪心】

Graveyard Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 170...

• ### HDU 3032 Nim or not Nim?(Multi-Nim)

Problem Description Nim is a two-player mathematic game of strategy in which ...

• ### 【Codeforces】1213B - Bad Prices

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### PAT 甲级 1003Emergency(Dijkstra最短路)

1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...

• ### 2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛- A. Banana

In the forest, there is a Banana Company that provides bananas from different pl...

• ### hdu----（5045）Contest（数位dp）

Contest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (J...

• ### Codeforces 833D Red-black Cobweb【树分治】

D. Red-black Cobweb time limit per test：6 seconds memory limit per test：256 mega...

• ### hdu 2473 Junk-Mail Filter (并查集之点的删除)

Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/...