Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.

Cerința

Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:

Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.

Cerința

Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
1. Dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.
2. O aranjare a roboților pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Date de intrare

Pe prima linie a fișierului de intrare roboti2.in se găsește un număr natural v a cărui valoare poate fi doar 1 sau 2. Pe a doua linie a fișierului de intrare se găsește un singur număr natural n reprezentând numărul de roboți. Pe a treia linie a fișierului de intrare se găsesc n numere naturale p[1], p[2], …, p[n­], separate prin câte un spațiu, p[i] reprezentând puterea armei robotului i.

Date de ieșire

Dacă valoarea lui v este 1, atunci fişierul de ieşire roboti2.out va conţine pe prima linie un singur număr natural reprezentând dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.

Dacă valoarea lui v este 2, atunci fişierul de ieşire va conţine pe prima linie n numere naturale separate prin câte un spaţiu, reprezentând puterile celor n roboți așezați pe cerc astfel încât suma produselor de câte două puteri vecine să fie maximă, iar aşezarea să fie minimă din punct de vedere lexicografic.

Restricții și precizări

• 2 ≤ n ≤ 100 000
• Pentru cerinţa 1, secvenţa de lungime maximă se alege pe cerc în sensul acelor de ceasornic.
• Dacă avem două şiruri de numere a[1], a[2], …, a[n] şi b[1], b[2], …, b[n] şi există 1≤k≤n, cea mai mică poziţie pentru care are loc a[1]=b[1], a[2]=b[2], …, a[k-1]=b[k-1] şi a[k]<b[k], atunci spunem că şirul a este mai mic lexicografic decât şirul b.
• În concurs, pentru rezolvarea corectă a cerinței 1 s-au acordat 30 puncte, pentru rezolvarea corectă a cerinței 2 s-au acordat 60 de puncte, iar din oficiu s-au acordat 10 puncte. Pe site, se acordă 10 puncte pentru exemple.
• Pentru cerința 2, dacă soluția afișată nu este minimă lexicografic, dar produce suma maximă corectă se acordă 50% din punctajul testului respectiv.
• Pentru cerința 2, teste în valoare totală de 36 puncte vor avea n ≤ 1000.
• 1 ≤ p[1], p[2],..., p[n] ≤ 1000.

Exemplul 1:

roboti2.in

1
7
4 7 2 6 5 1 3

roboti2.out

4

Explicație

v = 1, deci se va rezolva DOAR prima cerință. Cea mai lungă secvență strict crescătoare este 1 3 4 7 și are lungimea 4.

Exemplul 2:

roboti2.in

2 
5
3 9 1 12 5

roboti2.out

1 3 9 12 5

Explicație

v = 2, deci se va rezolva DOAR a doua cerință. 1*3+3*9+9*12+12*5+5*1=203 şi este suma maximă care se poate obţine. Această aranjare nu este singura pentru care se obține suma maximă, dar este cea mai mică lexicografic.

Exemplul 3:

roboti2.in

2 
4
1 2 1 1

roboti2.out

1 1 1 2

Explicație

v = 2, deci se va rezolva DOAR a doua cerință. 1*1+1*1+1*2+2*1=6 şi este suma maximă care se poate obţine.
Această aranjare nu este singura pentru care se obține suma maximă, dar este cea mai mică lexicografic.

#include<fstream>
using namespace std;

ifstream  fin("roboti2.in");
ofstream fout("roboti2.out");

int v, n, p[200005], q[200005], r[200005], f[200005];

int main(){
    int i,j,lmax,k,nr,m,M;
    fin>>v>>n;
    for(i=1;i<=n;i++) fin>>p[i];
    if(v==1){
        for(i=1;i<=n;i++) p[n+i]=p[i];
        lmax=0; j=1;
        for(i=2;i<=2*n;i++)
            if(p[i-1]>=p[i]){
                lmax=max(i-j,lmax);
                j=i;
            }
        fout<<lmax;
    }
    else{
        for(i=1;i<=1000;i++)q[i]=0;
        for(i=1;i<=n;i++)q[p[i]]++;
        nr=0;
        for(i=1;i<=1000;i++){
            if(q[i]>0){
                nr++; f[nr]=q[i]; r[nr]=i;
                q[i]=0;
            }
        }
        m=n+1;
        for(i=1;i<=f[nr];i++)  q[--m]=r[nr];
        M=n;
        for(i=nr-1;i>=2;i--){
            if(f[i]>1){
                q[++M]=r[i];
                for(j=1;j<f[i];j++)  q[--m]=r[i];
            }
            else{
                j=i;
                while(j-1>=2 && f[j-1]==1) j--;
                if(q[m]==q[M]){
                    if((i-j+1)%2==1) q[--m]=r[i--];
                    for(k=i;k>=j;k=k-2){
                        q[++M]=r[k];
                        q[--m]=r[k-1];
                    }
                }
                else{
                    if(q[m]>q[M]){
                        for(k=0;k<=i-j;k++){
                            if(k%2==0) q[--m]=r[i+k];
                            else  q[++M]=r[i+k];
                        }
                    }
                    else{
                        for(k=0;k<=i-j;k++){
                            if(k%2==1)  q[--m]=r[i+k];
                            else  q[++M]=r[i+k];
                        }
                    }
                }
                i=j;
            }
        }
        for(i=1;i<=f[1];i++)  q[--m]=r[1];
        for(i=m;i<=M;i++)  fout<<q[i]<<" ";
    }
    fout.close();
    return 0;
}