/*******************************************************
5) GFG — Nearest Left Index That Divides Current Element
 
Problem:
For each i, find nearest j<i such that A[i] % A[j] == 0, else -1.
 
Idea:
- For x=A[i], enumerate all divisors d of x.
- If we saw d earlier at lastIndex[d], then that's a valid j.
- Take maximum j among all divisors -> nearest to left.
 
Time: O(n * sqrt(maxA)) expected
*******************************************************/
 
#include <bits/stdc++.h>                 // standard CP header
using namespace std;                     // use std names directly
 
int main() {                             // program start
    ios::sync_with_stdio(false);         // fast I/O
    cin.tie(nullptr);                    // fast I/O
 
    int n;                               // array size
    cin >> n;                            // read n
    vector<int> A(n);                    // array
    for (int i = 0; i < n; i++) cin >> A[i]; // read elements
 
    unordered_map<int,int> lastIndex;    // lastIndex[value] = most recent index where value appeared
    lastIndex.reserve((size_t)n * 2);    // reserve to reduce rehashing (performance trick)
 
    for (int i = 0; i < n; i++) {        // process from left to right
        int x = A[i];                    // current value
        int best = -1;                   // best answer (nearest index), -1 if none
 
        for (int d = 1; 1LL * d * d <= x; d++) { // enumerate divisors up to sqrt(x)
            if (x % d) continue;         // if d is not a divisor, skip
 
            int d1 = d;                  // first divisor
            int d2 = x / d;              // paired divisor
 
            auto it1 = lastIndex.find(d1); // see if d1 was seen
            if (it1 != lastIndex.end()) best = max(best, it1->second); // update nearest index
 
            auto it2 = lastIndex.find(d2); // see if d2 was seen
            if (it2 != lastIndex.end()) best = max(best, it2->second); // update nearest index
        }
 
        cout << best << (i + 1 == n ? '\n' : ' '); // print answer (0-based index)
 
        lastIndex[x] = i;                // update last seen index for x
    }
 
    return 0;                            // done
}

LyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKNSkgR0ZHIOKAlCBOZWFyZXN0IExlZnQgSW5kZXggVGhhdCBEaXZpZGVzIEN1cnJlbnQgRWxlbWVudAoKUHJvYmxlbToKRm9yIGVhY2ggaSwgZmluZCBuZWFyZXN0IGo8aSBzdWNoIHRoYXQgQVtpXSAlIEFbal0gPT0gMCwgZWxzZSAtMS4KCklkZWE6Ci0gRm9yIHg9QVtpXSwgZW51bWVyYXRlIGFsbCBkaXZpc29ycyBkIG9mIHguCi0gSWYgd2Ugc2F3IGQgZWFybGllciBhdCBsYXN0SW5kZXhbZF0sIHRoZW4gdGhhdCdzIGEgdmFsaWQgai4KLSBUYWtlIG1heGltdW0gaiBhbW9uZyBhbGwgZGl2aXNvcnMgLT4gbmVhcmVzdCB0byBsZWZ0LgoKVGltZTogTyhuICogc3FydChtYXhBKSkgZXhwZWN0ZWQKKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPiAgICAgICAgICAgICAgICAgLy8gc3RhbmRhcmQgQ1AgaGVhZGVyCnVzaW5nIG5hbWVzcGFjZSBzdGQ7ICAgICAgICAgICAgICAgICAgICAgLy8gdXNlIHN0ZCBuYW1lcyBkaXJlY3RseQoKaW50IG1haW4oKSB7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBwcm9ncmFtIHN0YXJ0CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7ICAgICAgICAgLy8gZmFzdCBJL08KICAgIGNpbi50aWUobnVsbHB0cik7ICAgICAgICAgICAgICAgICAgICAvLyBmYXN0IEkvTwoKICAgIGludCBuOyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBhcnJheSBzaXplCiAgICBjaW4gPj4gbjsgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gcmVhZCBuCiAgICB2ZWN0b3I8aW50PiBBKG4pOyAgICAgICAgICAgICAgICAgICAgLy8gYXJyYXkKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBjaW4gPj4gQVtpXTsgLy8gcmVhZCBlbGVtZW50cwoKICAgIHVub3JkZXJlZF9tYXA8aW50LGludD4gbGFzdEluZGV4OyAgICAvLyBsYXN0SW5kZXhbdmFsdWVdID0gbW9zdCByZWNlbnQgaW5kZXggd2hlcmUgdmFsdWUgYXBwZWFyZWQKICAgIGxhc3RJbmRleC5yZXNlcnZlKChzaXplX3QpbiAqIDIpOyAgICAvLyByZXNlcnZlIHRvIHJlZHVjZSByZWhhc2hpbmcgKHBlcmZvcm1hbmNlIHRyaWNrKQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7ICAgICAgICAvLyBwcm9jZXNzIGZyb20gbGVmdCB0byByaWdodAogICAgICAgIGludCB4ID0gQVtpXTsgICAgICAgICAgICAgICAgICAgIC8vIGN1cnJlbnQgdmFsdWUKICAgICAgICBpbnQgYmVzdCA9IC0xOyAgICAgICAgICAgICAgICAgICAvLyBiZXN0IGFuc3dlciAobmVhcmVzdCBpbmRleCksIC0xIGlmIG5vbmUKCiAgICAgICAgZm9yIChpbnQgZCA9IDE7IDFMTCAqIGQgKiBkIDw9IHg7IGQrKykgeyAvLyBlbnVtZXJhdGUgZGl2aXNvcnMgdXAgdG8gc3FydCh4KQogICAgICAgICAgICBpZiAoeCAlIGQpIGNvbnRpbnVlOyAgICAgICAgIC8vIGlmIGQgaXMgbm90IGEgZGl2aXNvciwgc2tpcAoKICAgICAgICAgICAgaW50IGQxID0gZDsgICAgICAgICAgICAgICAgICAvLyBmaXJzdCBkaXZpc29yCiAgICAgICAgICAgIGludCBkMiA9IHggLyBkOyAgICAgICAgICAgICAgLy8gcGFpcmVkIGRpdmlzb3IKCiAgICAgICAgICAgIGF1dG8gaXQxID0gbGFzdEluZGV4LmZpbmQoZDEpOyAvLyBzZWUgaWYgZDEgd2FzIHNlZW4KICAgICAgICAgICAgaWYgKGl0MSAhPSBsYXN0SW5kZXguZW5kKCkpIGJlc3QgPSBtYXgoYmVzdCwgaXQxLT5zZWNvbmQpOyAvLyB1cGRhdGUgbmVhcmVzdCBpbmRleAoKICAgICAgICAgICAgYXV0byBpdDIgPSBsYXN0SW5kZXguZmluZChkMik7IC8vIHNlZSBpZiBkMiB3YXMgc2VlbgogICAgICAgICAgICBpZiAoaXQyICE9IGxhc3RJbmRleC5lbmQoKSkgYmVzdCA9IG1heChiZXN0LCBpdDItPnNlY29uZCk7IC8vIHVwZGF0ZSBuZWFyZXN0IGluZGV4CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IGJlc3QgPDwgKGkgKyAxID09IG4gPyAnXG4nIDogJyAnKTsgLy8gcHJpbnQgYW5zd2VyICgwLWJhc2VkIGluZGV4KQoKICAgICAgICBsYXN0SW5kZXhbeF0gPSBpOyAgICAgICAgICAgICAgICAvLyB1cGRhdGUgbGFzdCBzZWVuIGluZGV4IGZvciB4CiAgICB9CgogICAgcmV0dXJuIDA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIGRvbmUKfQ==