object Main extends App {
  import scala.io.StdIn._


  val prime = primes(math.sqrt(100000).toInt)
  val n = readInt
  val numbers = readLine.trim.split(' ').map(_.toInt)
  val sorted = numbers.zipWithIndex.sortBy(_._1).map(_._2)
  val primeUnions = Array.tabulate(100001){_ ⇒ new UnionFind}
  val numberUnions = Array.tabulate(n){_ ⇒ new UnionFind}
  for (p ← prime){
    for (i ← numbers.indices if numbers(i) % p == 0){
      primeUnions(p).merge(numberUnions(i))
      while(numbers(i) % p == 0){
        numbers(i) /= p
      }
    }
  }
  for (i ← numbers.indices if numbers(i) != 1) {
    numberUnions(i).merge(primeUnions(numbers(i)))
  }
  println(
    if (sorted.indices.forall(i ⇒ numberUnions(sorted(i)).isSameUnion(numberUnions(i)))) 1 else 0
  )
  class UnionFind{
    private var mParent = this
    private var mSize: Int = 1
    private def parent: UnionFind = {
      if (mParent == this) this
      else {
        mParent = mParent.parent
        mParent
      }
    }
    def isSameUnion(that: UnionFind): Boolean = {
      parent == that.parent
    }
    def merge(that: UnionFind): Unit = {
      if (!isSameUnion(that)){
        val thisP = parent
        val thatP = that.parent
        if (thisP.mSize > thatP.mSize) {
          thisP.mSize += thatP.mSize
          thatP.mParent = thisP
        }else {
          thatP.mSize += thisP.mSize
          thisP.mParent = thatP
        }
      }
    }
  }
  def primes(upper: Int): Array[Int] = {
    val memo = Array.tabulate(upper + 1){_ ⇒ true}
    for (i ← 2 to math.sqrt(upper).toInt if memo(i)){
      for (j ← 2 * i to upper by i){
        memo(j) = false
      }
    }
    (2 to upper).filter(memo).toArray
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline
    def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
  }
}

