roboti

Ș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ţe

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 roboti.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$, $\dots$, $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 roboti.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 \leq n \leq 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, \dots, a_n]$ şi $[b_1, b_2, \dots, b_n]$ şi există $1 \leq k \leq n$, cea mai mică poziţie, pentru care are loc $a_1 = b_1$, $a_2 = b_2$, $\dots$, $a_{k-1} = b_{k-1}$ şi $a_k < b_k$, atunci spunem că şirul $a$ este mai mic lexicografic decât şirul $b$.
• Pentru rezolvarea corectă a cerinței 1 se acordă 30 de puncte, pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte, iar din oficiu se acordă 10 puncte.
• 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 de puncte vor avea $n \leq 1\ 000$.
• $1 \leq p_1, p_2, \dots, p_n \leq 1\ 000$

Exemplul 1

roboti.in

1
7
4 7 2 6 5 1 3

roboti.out

4

Explicație

$v = 1$, deci se va rezolva DOAR prima cerință. $p = [\textcolor{red}{4}, \textcolor{red}{7}, 2, 6, 5, \textcolor{red}{1}, \textcolor{red}{3}]$.

Cea mai lungă secvență strict crescătoare este $[1, 3, 4, 7]$ și are lungimea $4$.

Exemplul 2

roboti.in

2
5
3 9 1 12 5

roboti.out

1 3 9 12 5

Explicație

$v = 2$, deci se va rezolva DOAR a doua cerință.

$1 \cdot 3 + 3 \cdot 9 + 9 \cdot 12 + 12 \cdot 5 + 5 \cdot 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

roboti.in

2
4
1 2 1 1

roboti.out

1 1 1 2

Explicație

$v = 2$, deci se va rezolva DOAR a doua cerință.

$1 \cdot 1 + 1 \cdot 1 + 1 \cdot 2 + 2 \cdot 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.