/*
Se citesc n elemente (1<=n<=1000) numere naturale intr-un vector v.
Se dau urmatoarele cerinte ce se vor rezolva in acelasi program, in ordinea data, cu afisarea vectorului dupa fiecare pas pe linii diferite:
1) Sa se insereze dupa fiecare element patrat perfect, radacina sa patrata (ex. daca v[i]==25, se insereaza pe v[i+1] valoarea 5
                                                                        - vezi pbinfo, am lucrat ceva similar, atentie, aici se insereaza DUPA)
ex: IN
5
7 3 4 1 9
OUT: 7 3 4 2 1 1 9 3
2) Sa se caute valoarea x citita de la tastatura, si daca se gaseste, sa se afiseze numarul aparitiilor si sa se stearga aparitiile din vector
(NU cu cautare binara, ci o cautare simpla)
ex: IN
x=1
se considera v anterior (valabil pt toti pasii care urmeaza)
OUT:
k=2
7 3 4 2 9 3
3) Sa se calculeze si afiseze suma elementelor impare din vector
OUT: S=22
4) Sa se ordoneze crescator elementele vectorului si sa se afiseze
OUT: 2 3 3 4 7 9
5) Sa se afiseze in ordine descrescatoare elementele de pe pozitiile pare.
OUT: 9 4 3
*/

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,v[1001],i,j, x,r, k=0, S=0, ok, aux;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i];
//1)
    for(i=1; i<=n; i++)
    {
        r = sqrt(v[i]);
        if(r * r == v[i])
        {
            n++;
            for(j = n-1; j >= i; j--)
                v[j+1] = v[j];
            v[i+1] = r;
            i++;
        }
    }
    for(i = 1; i <= n; ++i)
        cout << v[i] << " ";
    cout<<"\n";
//2)
    cout<<"Citeste x=";
    cin>>x;
    for(i=1; i<=n; i++)
    {
        if(v[i]==x)
        {
            k++; //cresc nr aparitii
            //STERGERE:
            for(j = i; j <=n-1; j++)
                v[j] = v[j+1];
            n--;
            i--;
        }
    }
    cout<<"k="<<k<<"\n";
    for(i = 1; i <= n; ++i)
        cout << v[i] << " ";
    cout<<"\n";

//3)
    for(i=1; i<=n; i++)
    {
        if(v[i]%2!=0)
            S+=v[i];
    }
    cout<<"S="<<S<<"\n";

//4)
    do
    {
        ok = 1;
        for(i=1; i<=n-1; i++)
        {
            if(v[i]>v[i+1])
            {
                aux = v[i];
                v[i]= v[i+1];
                v[i+1]= aux;
                ok=0;
            }
        }
    }
    while(ok==0);
    for(i = 1; i <= n; ++i)
        cout << v[i] << " ";
    cout<<"\n";
//5)
    if(n%2!=0)
        n--;
    for(i = n; i >=2; i-=2)
        cout << v[i] << " ";

    return 0;
}