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 X ** I (0 ≤ x** I ≤ 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, 12Copy the code

Output

1 2 3 12Copy the code

Input

4, 1, 1, 2, 2Copy the code

Output

1 1 2 3Copy the code

Input

2
1 2
Copy the code

Output

2
1 2
Copy the code

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.

Title links: codeforces.com/contest/626…

The question

Given the set of N numbers, find a (mean – median) maximum subset (maximum skewness), output the number of subset elements and each element (any order).

Analysis of the

Because it’s a subset, it doesn’t have to be a continuous sequence. And then we have the following conclusions.

1. The maximum skewness must be ≥0

Because the skewness of an element is zero.

2. The maximum skewness subset must have an odd number of elements.

Certificate:

If the skewness is greatest when the number of elements is even 2*k, we show that it cannot be worse if one element a[k+1] is removed.

The sorted subsets are a[I]. The average of all numbers minus a[k+1] is AV

New mean – old mean = AV -(av+a[k+1])/2=(AV -a[k+1])/2

New median – old median = A [k]-(a[k]+a[K +1])/2=(A [k]-a[k+1])/2

– old and old average median = (av + a/k + 1) / 2 – (a/k + a/k + 1) / 2 = (av – a [k]) / 2 0 or higher (otherwise impossible of skewness maximum)

So there is mean increment – median increment =(av-a[k])/2≥0

So the new skewness can’t be worse.

3. The average value increases first and then decreases

Since it is an odd number, enumerate each number as the median. If the left and right extension length is J, then to make the skewness larger, we must choose the left and right largest numbers each time. So the remaining numbers get smaller and smaller, the average increases less and less, and the current average gets bigger and bigger, and then after some peak the average starts to decrease.

So you can use dichotomy to take the midpoint and the point next to the midpoint at a time and determine whether the current average is increasing or decreasing, increasing to the right, decreasing to the left.

Incidentally make fun of 1: CF evaluation machine is no good, ran this ran half an hour just finished!!

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=200020; 5 inline int read() 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; 27 sum(int I,int j) 28 {29 return s[n]-s[n-j]+s[I]-s[i-j-1]; 30 } 31 int main() 32 { 33 n=read(); 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}Copy the code