Програмчлалын олимпиадын бодлогын архив

Сэлгэмэл гэдэг нь ямар нэг олонлогийг өөр дээр нь буулгасан харилцан нэг утгатай буулгалт юм. Өөрөөр хэлбэл сэлгэмэл гэж олонлогийн элементүүдийн байрыг сэлгэх аргыг хэлнэ. Жишээ нь {1, 2, 3, 4, 5} гэсэн олонлогоос дараах сэлгэмлийг үүсгэж болно:

Энд P сэлгэмлийг дараах байдлаар тодорхойлсон байна: P(1)=4, P(2)=1, P(3)=5 гэх мэт.
Харин P(P(1))-ийн утга хэдтэй тэнцүү вэ? P(P(1))=P(4)=2 гэдэг нь ойлгомжтой юм. Мөн P(P(3))=P(5)=3 байна. Хэрэв P(n) нь сэлгэмэл бол P(P(n)) нь мөн сэлгэмэл байх нь тодорхой. Манай жишээн дээр:

байна(шалгаж үз).
Энд дараах тэмдэглэгээг хэрэглэнэ: P(P(n))=P²(n). Ерөнхий тохиолдолд: P(n)=P¹(n), P^k(n)=P(P^k-1(n)).
Сэлгэмлүүд дотроос онцгой хамгийн онцгой нэг нь бүх элемент байрандаа байх тийм сэлгэмэл юм:

Дурын k тооны хувьд (E_N)^k=E_N байх нь илэрхий. Мөн дараах өгүүлбэр ч үнэн байна:
"P(n) нь N элементтэй олонлогийн ямар нэг сэлгэмэл байг. Тэгвэл P^k=E_N байх ямар нэг k тоо үргэлж олдоно."
P^k=E_N байх хамгийн бага k бүхэл тоог P(n) сэлгэмлийн зэрэг гэж нэрлэнэ.
Сэлгэмэл өгөгдсөн бол түүний зэргийг ол.

Input

Эхний мөрөнд олонлогийн элементийн тоог илэрхийлэх 1 ≤ N ≤ 1000 байх N бүхэл тоо өгөгдөнө. Дараагийн мөрөнд хоорондоо зайгаар тусгаарлагдсан, 1-ээс N хүртлэх тоонуудын сэлгэмэл болох P(1), P(2) … P(N) тоонууд өгөгдөнө.

Output

Гаралт дээр Р сэлгэмлийн зэрэг болох ганц тоог хэвлэнэ. Хариуг 1 000 000 000 тооноос хэтрэхгүй гэж үзэж болно.

Example

Input:
5
4 1 5 2 3


Output:
6