Codeforces 1419 D2. Sage's Birthday (hard version) Solution

 Solution in C++:

///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch

///Islamic University,Bangladesh  

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    long long i,n,m,j;

    cin>>n;

    long long a[n+2];

    for(i=0; i<n; i++)

    {

        cin>>a[i];

    }

    sort(a,a+n);

    long long  v=0;

    long long r[n+2];

    for(i=1; i<n; i=i+2)

    {

        r[i]=a[v++];

    }

    for(j=0; j<n; j=j+2)

    {

        r[j]=a[v++];

    }

    long long  c=0;

    for(i=1; i<n-1; i++)

    {

        if((r[i+1]>r[i])&&(r[i-1]>r[i]))

            c++;

    }

    cout<<c<<endl;

    for(i=0; i<n; i++)

    {

        cout<<r[i]<<" ";

    }

    cout<<endl;

}