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

1-ээс N (N ≥ 2) хүртлэх тоонуудаар дугаарлагдсан N ширхэг оройнууд бүхий модыг (өөрөөр хэлбэл циклгүй граф) авч үзье. Уг модны хувьд Прюферийн кодыг дараах аргаар байгуулдаг: төгсгөлийн оройнуудаас (модонд ганц ирмэгээр холбогдож байгаа оройнуудаас) хамгийн бага дугаартай оройг сонгон авна. Дараа нь энэ оройг болон түүнийг модтой холбож байсан ирмэгийг устгаж, уг ирмэгийн нөгөө үзүүрт модонд үлдэж байгаа оройн дугаарыг бичнэ. Үлдэж байгаа модны төгсгөлийн оройнуудын дотроос хамгийн бага дугаартайг нь сонгон авч, устгах гэх мэтээр модонд ганц орой үлдтэл үргэлжлүүлнэ. Хамгийн сүүлд үлдэж байгаа оройн дугаар N байх нь илэрхий. Бичигдсэн 1-ээс N хүртлэх утгатай N-1 ширхэг тоонуудыг анхны модны Прюферийн код гэж нэрлэнэ. Таны даалгавар бол хамгийн олон ирмэг гарсан байх оройн дугаарыг олох явдал юм. Ийм орой олон байвал хамгийн бага дугаартайг нь хэвлэнэ. 2 ≤ N ≤ 7500 гэж үзнэ.

Input

Оролт дээр ямар нэг модны Прюферийн код өгөгдөнө. Тоонууд нэг нэг мөрөнд өгөгдөнө.

Output

Хамгийн олон ирмэг гарсан оройн дугаарыг хэвлэнэ. Ийм орой олон байвал хамгийн бага дугаартайг нь хэвлэнэ.

Example

Input:
2 
1 
6 
2 
6


Output:
2