DBG = !true
DBG2 = !true
EOF = 999999
VAL = 0
CARD = 1
PREV = 2
NXT = 3

# p**e exceeds 200000
pe = [ 0, 0, 18, 14, 9, 8, 7, 7, 7,  ]

def foo(card, p, val, suf, b)
  denom = card - 1
  ex = val - b[suf][VAL]
  # denom / p**ex
  if p == 1
    return denom
  elsif ex > 18||p > 100 && ex > 3||p > 10 && ex > 5
    return 0
  else
    return denom / (p ** ex)
  end
end

def pass(p, bb, c)
  puts "call pass(#{p})\n" if DBG
  #b = Marshal.load(Marshal.dump(bb))
  b = bb.map{|x| [x[0], x[1], x[2], x[3]]}
  #b = bb.map{|x| x.map{|y| y}}
  #b = bb.map{|x| x.flatten}
  if DBG
    print "b: "
    print b
    puts "\n- - - -"
  end
  $used = Array.new(c.size, false)
  #$used.map!{|x| false}
  lastsuf = -1
  for i in 0..(c.size-1)
    suf = c[i][0]
    puts "doing suf:#{suf}" if DBG
    next if $used[suf]
    val = b[suf][VAL]
    card = b[suf][CARD]
    prev = b[suf][PREV]
    nxt = b[suf][NXT]
    if prev == -1 && nxt == EOF
      lastsuf = suf
      break
    end

    if prev == -1
      b[nxt][CARD] += 1 + foo(card, p, val, nxt, b)
      b[nxt][PREV] = -1
    elsif nxt == EOF
      b[prev][CARD] += foo(card, p, val, prev, b)
      b[prev][NXT] = EOF
    elsif b[prev][VAL] > b[nxt][VAL]
      b[prev][CARD] += foo(card, p, val, prev, b)
      b[prev][NXT] = nxt
      b[nxt][PREV] = prev
    elsif b[prev][VAL] < b[nxt][VAL]
      b[nxt][CARD] += 1 + foo(card, p, val, nxt, b)
      b[prev][NXT] = nxt
      b[nxt][PREV] = prev
    else # b[prev][VAL] == b[nxt][VAL]
      b[nxt][CARD] +=
            b[prev][CARD] + foo(card, p, val, nxt, b)
      b[nxt][PREV] = b[prev][PREV]
      $used[prev] = true
      if b[prev][PREV] != -1
        b[b[prev][PREV]][NXT] = nxt
      end
      #lastsuf = nxt
    end
    if DBG
      print "b: "
      print b
      puts " --"
      print "used: "
      print $used
      puts "\n- - - -"
    end
  end
  #lastsuf = c[-1][0] if !used[c[-1][0]]
  ex = b[lastsuf][VAL]
  easyconds =
     (p>1 && ex>18 || p>100 && ex>3 || p>10 && ex>5)
  ret = (easyconds ||
          (b[lastsuf][CARD] <= p**b[lastsuf][VAL]))
  if DBG
    print "b[last]cd:#{b[lastsuf][CARD]} "
    puts "b[last]vl:#{b[lastsuf][VAL]}"
    puts "returns:#{ret}"
  end
  return ret
end

# # # #  main  # # # #

n = gets.to_i
a = gets.split.map{|x| x.to_i}
if DBG
  print "a: "
  print a
  puts ""
end

prevn = 1
bb = []
j = 0
for i in 1...a.size
  if a[i] == a[i-1]
    prevn += 1
  else
    bb << [a[i-1], prevn, j-1, j+1]
    prevn = 1
    j += 1
  end
end

bb << [a[a.size-1], prevn, j-1, EOF]
# 1 1 1 5 5 3 3 3 3 ..  -> [ [1,3], [5,2], [3,4], ..]
if DBG
  puts ""
  print bb
  puts ""
end

n1 = 0
n2 = 0
n3 = 0
n4 = 0
n5 = 0
c = []
for i in 0...bb.size
  c << [i, bb[i][0]]
  n1 += bb[i][1] if bb[i][0] == 1
  n2 += bb[i][1] if bb[i][0] == 2
  n3 += bb[i][1] if bb[i][0] == 3
  n4 += bb[i][1] if bb[i][0] == 4
  n5 += bb[i][1] if bb[i][0] == 5
end
c.sort_by!{|x| -x[1]}  # 最大値が[0]に
if DBG
  puts "lastsuf:#{c[-1][0]}" if DBG
  print "bb: "
  print bb
  puts ""
  print "c: "
  print c
  puts ""
end
$used = Array.new(c.size)

#pbgn = 0  # can't
#pend = 200001  # can
pbgn = [0, n1-1].max  # can't
pend =
 (n1 + n2**0.5 + n3**0.333 + n4**0.25 + n5**0.2).to_i + 4

#p = (n1 + Math.sqrt(n2)).to_i * 2
#p = 16 if p < 16
#  pend = p
#else
#  pbgn = p
#end

while pbgn + 1 < pend
  p = (pbgn + pend)/2
  puts "p:#{p}" if DBG2
  if pass(p, bb, c)
    pend = p
  else
    pbgn = p
  end
end
# pbgn + 1 = pend
print pend


Measured memory_bytes: 85160