#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b) {
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    long long x = power(a, b / 2);
    x *= x;
    if(b & 1)
        x *= a;
    return x;
}

int main() {
    long long n;
    cin >> n;
    long long a = 1;
    while(true) {
        long long x = power(5LL, a);
        if(x > n)
            break;
        long long y = n - x;
        long long b = 1;
        while(power(3LL, b) <= y) {
            b++;
        }
        long long shoot = power(3LL, b);
        shoot /= 3;
        if(shoot == y && b > 1) {
            cout << b - 1 << " " << a << endl;
            return 0;
        }
        a++;
    }
    cout << "-1" << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int a[200001],res=0,n;
bool vis[200001];
void calc(int x){
	if(x==res){
		++res;
		while(vis[res]==true)++res;
	}
	else vis[x]=true;
}
int main()
{
	n=read();
	For(i,1,n) a[i]=read();
	For(i,1,n){
		calc(a[i]);
		printf("%d\n",res);
	}
	return 0;
}