#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define PB push_back
constexpr int kN = int(1E5 + 10);
vector<int> ori[kN], ned[kN];
int p[kN], a[kN];
int Find(int n) {return p[n] == n ? n : p[n] = Find(p[n]);}
void merge(int l, int r) {
	p[Find(r)] = Find(l);
	return ;
}
int main() {
	int n, head;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) ori[a[i]].PB(i);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) ned[a[i]].PB(i);
	for (int i = 1; i < kN; i++) p[i] = i;
	for (int i = 2; i < kN; i++) {
		head = 0;
		for (int j = i; j < kN; j += i) if (!ori[j].empty()) {
			if (head == 0) head = j;
			else merge(head, j);
		}
	}
	for (int i = 1; i < kN; i++) if (p[i] != i) {
		for (int j : ori[i]) ori[Find(i)].PB(j);
		for (int j : ned[i]) ned[Find(i)].PB(j);
	}
	for (int i = 1; i < kN; i++) if (p[i] == i) {
		sort(ori[i].begin(), ori[i].end());
		sort(ned[i].begin(), ned[i].end());
		if (ori[i] != ned[i]) {
			printf("0\n");
			return 0;
		}
	}
	printf("1\n");
}

