Se dă un șir cu n elemente naturale.

Cerinţa

Să se insereze în șir înaintea fiecărui element pătrat perfect rădăcina sa pătrată.

Date de intrare

Programul va citi de la tastatură numărul n, apoi n numere naturale reprezentând elementele șirului.

Date de ieşire

Programul va afișa pe ecran elementele șirului obținut după inserare, separate prin câte un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 25
• elementele șirului vor fi cuprinse între 0 și 1.000.000

Exemplu

Date de intrare

5
7 3 4 1 9

Date de ieșire

7 3 2 4 1 1 3 9

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[51];
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    for(int i = 1; i <= n; ++i){
        int ca = a[i];
        int r = sqrt(ca);
        if(r * r == ca){
            n++;
            for(int j = n; j > i; --j)
                a[j] = a[j - 1];
            a[i] = r;
            i++;
        }
    }

    for(int i = 1; i <= n; ++i)
        cout << a[i] << " ";

    return 0;
}