시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 176 95 87 57.616%

문제

해빈이는 배가 한 척이라도 올까 말까 한 작은 항구 마을에 산다. 그런데 어느 날, 마을을 방문한 적이 있는 모든 배가 한꺼번에 마을을 방문한 날이 있었다. 해빈이는 이 날을 기념해 1일로 센다. 그리고 배가 한 척이라도 마을에 온 날을 신나는 날이라고 하고 특별히 리스트에 기록해두었다.

해빈이는 마을에 방문하는 배들을 관찰한 결과, 이들이 일정한 날자 간격을 두고 주기적으로 항구를 방문한다는 사실을 알아차렸다. 예를 들어, 간격이 3인 배는 1일, 4일, 7일, 10일 등에 해빈이의 마을에 온다.

오늘은 신나는 날이다. 오늘을 포함해서 해빈이의 신나는 날 리스트가 주어질 때, 방문한 배의 최소 수를 구하라. (해빈이는 모든 신나는 날을 리스트에 정확히 적어두었다. 따라서 항상 답이 존재한다.)

입력

입력의 첫 줄에 정수 신나는 날의 개수 N (2 ≤ N ≤ 5000)이 주어진다.

다음 N줄에는 신나는 날의 번호가 오름차순으로 한 줄에 하나 씩 주어진다. 첫 번째 수와 마지막 수는 각각 해빈이가 관찰을 시작한 날, 그리고 해빈이가 매긴 오늘의 번호이다. 즉, 첫 번째 줄은 항상 1이다. 마지막 수(오늘의 번호)는 10^9보다 작다.

출력

가능한 배의 최소 수를 출력한다.

예제 입력 1

3
1
3
4

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWJjMzBcdWFjMDAgXHVkNTVjIFx1Y2M5OVx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWM2MmNcdWFlNGMgXHViOWQwXHVhZTRjIFx1ZDU1YyBcdWM3OTFcdWM3NDAgXHVkNTZkXHVhZDZjIFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYjBcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWM1YjRcdWIyOTAgXHViMGEwLCBcdWI5YzhcdWM3NDRcdWM3NDQgXHViYzI5XHViYjM4XHVkNTVjIFx1YzgwMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YmMzMFx1YWMwMCBcdWQ1NWNcdWFlYmNcdWJjODhcdWM1ZDAgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWIwYTBcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YjBhMFx1Yzc0NCBcdWFlMzBcdWIxNTBcdWQ1NzQmbmJzcDsxXHVjNzdjXHViODVjIFx1YzEzY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmMzMFx1YWMwMCBcdWQ1NWMgXHVjYzk5XHVjNzc0XHViNzdjXHViM2M0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWM2MjggXHViMGEwXHVjNzQ0IFx1YzJlMFx1YjA5OFx1YjI5NCBcdWIwYTBcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwIFx1ZDJiOVx1YmNjNFx1ZDc4OCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgXHVhZTMwXHViODVkXHVkNTc0XHViNDUwXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWJjMzBcdWI0ZTRcdWM3NDQgXHVhZDAwXHVjYzMwXHVkNTVjIFx1YWNiMFx1YWNmYywgXHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWIwYTBcdWM3OTAgXHVhYzA0XHVhY2E5XHVjNzQ0IFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVkNTZkXHVhZDZjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVjNTQ0XHVjYzI4XHViODM4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFjMDRcdWFjYTlcdWM3NzQgM1x1Yzc3OCBcdWJjMzBcdWIyOTQgMVx1Yzc3YywgNFx1Yzc3YywgN1x1Yzc3YywgMTBcdWM3N2MgXHViNGYxXHVjNWQwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1Yzc1OCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjMmUwXHViMDk4XHViMjk0IFx1YjBhMFx1Yzc3NFx1YjJlNC4gXHVjNjI0XHViMjk4XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyZuYnNwO1x1ZDU3NFx1YmU0OFx1Yzc3NFx1Yzc1OCBcdWMyZTBcdWIwOThcdWIyOTQgXHViMGEwIFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHViYzMwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLiAoXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyZTBcdWIwOThcdWIyOTQgXHViMGEwXHVjNzQ0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVjODAxXHVjNWI0XHViNDUwXHVjNWM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IFx1YzJlMFx1YjA5OFx1YjI5NCBcdWIwYTBcdWM3NTggXHVhYzFjXHVjMjE4IE4mbmJzcDsoMiAmbGU7IE4gJmxlOyA1MDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YzJlMFx1YjA5OFx1YjI5NCBcdWIwYTBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OCBcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1YzY0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjMjE4XHViMjk0IFx1YWMwMVx1YWMwMSBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVhZDAwXHVjYzMwXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIwYTAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHViOWU0XHVhZTM0IFx1YzYyNFx1YjI5OFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgXHVkNTZkXHVjMGMxIDFcdWM3NzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWMyMTgoXHVjNjI0XHViMjk4XHVjNzU4IFx1YmM4OFx1ZDYzOClcdWIyOTQmbmJzcDsxMF45XHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCUk9ET1ZJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBsaXZlcyBpbiBhIHNtYWxsIHRvd24gd2l0aCBhIGhhcmJvdXI6IG9uY2UgaW4gYSBibHVlIG1vb24gYSBzaGlwIHBhc3NlcyBieS4gSG93ZXZlciwgdG8gdGhpcyBkYXlNaXJrbyByZW1lbWJlcnMgdGhlIGRheSB3aGVuIGFsbCB0aGUgc2hpcHMgd2hvIGhhZCBldmVyIHZpc2l0ZWQgdGhlIGhhcmJvdXIgc2hvd2VkIHVwLiBIZSBkZW5vdGVkIHRoaXMgZGF5IGJ5IGluZGV4IDEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1hbnkgZGF5cyBoYXZlIHBhc3NlZCBzaW5jZSwgYnV0IE1pcmtvIG5vdGVkIGVhY2ggZGF5IHdoZW4gYXQgbGVhc3Qgb25lIHNoaXAgdmlzaXRlZCB0aGUgaGFyYm91ciwgbmFtaW5nIHRoZXNlIGRheXMgZW50ZXJ0YWluaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZGRpdGlvbmFsbHksIE1pcmtvIGhhcyBub3RpY2VkIHRoYXQgZWFjaCBzaGlwIHZpc2l0cyB0aGUgaGFyYm91ciBwZXJpb2RpY2FsbHksIGF0IHJlZ3VsYXIgaW50ZXJ2YWxzLiBGb3IgaW5zdGFuY2UsIGFuIGludGVydmFsIG9mIGxlbmd0aCAzIGltcGxpZXMgdGhhdCBzb21lIHNoaXAgdmlzaXRlZCB0aGUgaGFyYm91ciBvbiBkYXlzIDEsIDQsIDcsIDEwIGV0Yy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gTWlya28mcnNxdW87cyBsaXN0IG9mIGVudGVydGFpbmluZyBkYXlzIChpbmNsdWRpbmcgdG9kYXkgd2hpY2ggaXMgY29uc2lkZXJlZCB0byBiZSBhbiBlbnRlcnRhaW5pbmcgZGF5IGFzIHdlbGwpLCBjb21wdXRlIHRoZSBtaW5pbXVtIHBvc3NpYmxlIG51bWJlciBvZiBzaGlwcyB2aXNpdGluZyBoaXMgaGFyYm91ci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZXM6IEFsbCBlbnRlcnRhaW5pbmcgZGF5cyBhcHBlYXIgb24gTWlya28mcnNxdW87cyBsaXN0LiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIGdpdmVuIGRhdGEgaXMgY29uc2lzdGVudCAtIGluIG90aGVyIHdvcmRzLCBhIHNvbHV0aW9uIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDUwMDApLCB0aGUgbnVtYmVyIG9mIGVudGVydGFpbmluZyBkYXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiBpbmRpY2VzIG9mIGVudGVydGFpbmluZyBkYXlzLCBvbmUgcGVyIGxpbmUsIGluIGFzY2VuZGluZyBvcmRlci4gVGhlIGZpcnN0IGFuZCB0aGUgbGFzdCBpbmRpY2VzLCByZXByZXNlbnRpbmcgdGhlIGRheSBmcm9tIHdoaWNoIE1pcmtvIHN0YXJ0ZWQgbW9uaXRvcmluZyBoYXJib3VyIHRyYWZmaWMgYW5kIHRvZGF5LCByZXNwZWN0aXZlbHksIHdpbGwgYWx3YXlzIGFwcGVhciBvbiB0aGUgbGlzdC4gVGhlIGZpcnN0IGluZGV4IHdpbGwgYWx3YXlzIGJlIDEsIGFuZCB0aGUgbGFzdCBvbmUgKGluZGV4IG9mIHRvZGF5KSB3aWxsIGJlIGxlc3MgdGhhbiAxMDxzdXA+OTxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWluaW11bSBudW1iZXIgb2Ygc2hpcHMuJm5ic3A7PFwvcD5cclxuXHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==