#include <bits/stdc++.h>
using namespace std;
int a[100010];
int zd[1] = {INT_MIN};
int zdh(int n)
{
	for(int j=1;j<=n;j++)
	{
		if(a[j]>zd[1] && a[j]!=(int)sqrt(zd[1]))
		{
			zd[1] = a[j];
		}
	}
	return zd[1];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	long long h = 0;
	int zd2 = 0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	} 
	for(int i=1;i<=n;i++)
	{	
		zd2 = zdh(n);
		zd[1] = zd2;
		h = h+zd2;
		for(int j=i+1;j<=n;j++)
		{
			a[j] = (int)sqrt(a[j]);
		}
		cout<<h<<' '<<zd2<<'\n';
	}
	cout<<h;
	return 0;
}