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

"Тоо хэлэлцэх" гэдэг тоглоом нь дараах дүрэмтэй: тоглолт бүр дээр тоглогч бүр 100-гаас хэтрэхгүй дурын натурал тоо хэлнэ. Ингээд энэ тоглолтонд давтагдаж хэлэгдээгүй хамгийн бага тоог хэлсэн тоглогч хожих ба энэ тоотой тэнцүү хэмжээний оноог авна. Жишээ нь, хэрэв 6 хүн тоглож байгаад тус бүр 3, 2, 1, 1, 4, 2 гэсэн тоонуудыг хэлсэн бол эхний тоглогч хожих ба 3 гэсэн оноог авна. Хэрэв хүмүүсийн хэлсэн бүх тоонууд давтагдсан байвал тэнцсэн гэж үзэх ба хэн ч хожихгүй.
Тоглогчийн нийт оноо нь бүх тоглолтоос авсан оноонуудын нийлэрээр тодорхойлогдоно.
Та найзуудтайгаа энэ тоглоомыг тоглож байгаа ба, хүмүүсийн хэлсэн тоог зарлан хэлж, хэн хожсоныг тодорхойлох үүрэгтэй. Гэвч ийм үүрэгтэй байгаагаа далимдуулан хүмүүсийн хэлж байгаа тоог сонсоод өөрийн хэлэх гэж байгаа тоогоо илүү оновчтой болгож болно. Иймд өөрийн хожлыг ихэсгэхийн тулд тоогоо хамгийн сүүлд хэлж байгаагаа ашиглах хэрэгтэй.
Хамгийн сүүлийн тоглолт явагдаж байгаа ба бусад тоглогчдын өмнөх тоглолтуудад хэлсэн оноо мэдэгдэж байгаа. Мөн энэ тоглолтонд тоглогчдын хэлсэн тоонууд мэдэгдэж байгаа. Тоглоомын төгсгөлд оноогоороо аль болох олон тоглогчийн дээр гарахын тулд та ямар тоо хэлэх ёстой вэ? Хэрэв таны хэлж болох тоо олон байвал хамгийн багыг нь ол.

Input

Оролтын эхний мөрөнд тоглогчдын тоо n байна (2 ≤ n ≤ 100). Хоёр дахь мөрөнд өмнөх тоглолтуудад тоглогчдын авсан оноонууд болох n тоо байна (зуугаас хэтрэхгүй, эерэг бүхэл тоонууд). Оноонуудыг тоглогчдын тоогоо хэлэх дарааллаар байрлуулсан байна (өөрөөр хэлбэл таны оноо хамгийн сүүлд нь байгаа). Гурав дахь мөрөнд тоглогчдын сүүлийн тоглолтон дээр хэлсэн тоонууд болох n-1 ширхэг тоо хэлэгдсэн дарааллаараа байна(утгууд нь зуугаас хэтрэхгүй).

Output

Та өөрийн хэлэх ёстой тоогоо хэвлэнэ.

Example

Input:
6
0 0 0 0 0 0
2 3 4 5 6 

Output:
1

Input:
6
8 3 12 5 0 9
2 1 3 1 4  

Output:
2

Хоёр дахь жишээн дээр та сүүлийн тоглолтон дээр хожиж чадахгүй. Гэхдээ 2 гэж хэлснээрээ эхний тоглогчийг хожих боломжгүй болгох ба бүх тоглолтын нийт дүнгээр 2-рт үлднэ. Дөрвөн тоглогчийн оноо таныхаас бага байх болно.