시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 353 88 55 25.822%

문제

상근이는 자기가 살 집을 설계하려고 한다.

먼저, 정수 좌표마다 점이 찍혀 있는 매우 큰 종이가 필요하다. 그 다음, 이 종이의 원점에 연필을 올린다. 이제 연필을 빠르게 N번 움직여 평면도를 그린다. 연필은 절대로 종이에서 떼지 않는다. 또, 상근이는 연필을 현재 있는 점과 인접한 8개 점 중 하나로만 이동할 수 있다. (가로, 세로, 대각선) 가능한 이동은 아래 그림과 같으며, 숫자로 나타낼 수 있다.

상근이가 그린 평면도가 주어진다. 이 때, 방의 수를 구하는 프로그램을 작성하시오. 방은 평면도 상에서 빈 공간이며, 연필 선으로 모든 면이 둘러 쌓여 있어야 한다. 방은 다른 방으로 둘러 쌓여질 수도 있다. 상근이는 이미 그었던 선을 또 그릴 수도 있다.

입력

첫째 줄에 연필을 움직인 횟수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 연필을 움직인 순서가 주어진다. 이 순서는 길이가 N인 숫자이며 0부터 7까지로 이루어져 있다. 

출력

첫재 줄에 평면도의 방의 개수를 출력한다. 

예제 입력 1

19
6664442220001655360

예제 출력 1

3

힌트

예제를 그림으로 그리면 위와 같다

W3sicHJvYmxlbV9pZCI6IjMxMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYzlcdWJhNzRcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVjMGI0IFx1YzlkMVx1Yzc0NCBcdWMxMjRcdWFjYzRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWNcdWI5YzhcdWIyZTQgXHVjODEwXHVjNzc0IFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3MCBcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWM3NzQgXHVjODg1XHVjNzc0XHVjNzU4IFx1YzZkMFx1YzgxMFx1YzVkMCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVjNjJjXHViOWIwXHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YmU2MFx1Yjk3NFx1YWM4YyBOXHViYzg4IFx1YzZjMFx1YzljMVx1YzVlYyBcdWQzYzlcdWJhNzRcdWIzYzRcdWI5N2MgXHVhZGY4XHViOWIwXHViMmU0LiBcdWM1ZjBcdWQ1NDRcdWM3NDAgXHVjODA4XHViMzAwXHViODVjIFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YzExYyBcdWI1YmNcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIDhcdWFjMWMgXHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwKSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzc0XHViM2Q5XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzNjXHViYTcwLCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYXJjMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgd2lkdGg6MjE5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWRmOFx1YjliMCBcdWQzYzlcdWJhNzRcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJjMjlcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWJjMjlcdWM3NDAgXHVkM2M5XHViYTc0XHViM2M0IFx1YzBjMVx1YzVkMFx1YzExYyBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzc0XHViYTcwLCBcdWM1ZjBcdWQ1NDQgXHVjMTIwXHVjNzNjXHViODVjIFx1YmFhOFx1YjRlMCBcdWJhNzRcdWM3NzQgXHViNDU4XHViN2VjIFx1YzMxM1x1YzVlYyBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJjMjlcdWM3NDAgXHViMmU0XHViOTc4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWI0NThcdWI3ZWMgXHVjMzEzXHVjNWVjXHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWJiZjggXHVhZGY4XHVjNWM4XHViMzU4IFx1YzEyMFx1Yzc0NCBcdWI2MTAgXHVhZGY4XHViOWI0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzVmMFx1ZDU0NFx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM3NzggXHVkNjlmXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzVmMFx1ZDU0NFx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM3NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxY1x1YzExY1x1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMmJcdWM3OTBcdWM3NzRcdWJhNzAgMFx1YmQ4MFx1ZDEzMCA3XHVhZTRjXHVjOWMwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjN2FjIFx1YzkwNFx1YzVkMCBcdWQzYzlcdWJhNzRcdWIzYzRcdWM3NTggXHViYzI5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYXJjMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjVweDsgd2lkdGg6MjI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjXHViOTdjIFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWFkZjhcdWI5YWNcdWJhNzQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1YjJlNDxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEzNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFSSElURUtUIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgYXJjaGl0ZWN0IE1pcmtvIGhhcyBnaXZlbiBoaXMgdGhyZWUteWVhciBvbGQgc29uLCBNaXJrbywgSnIuLCB0aGUgdGFzayBvZiBjcmVhdGluZyB0aGUgZmxvb3IgcGxhbiBmb3IgdGhlIGJ1aWxkaW5nIGhlIGlzIGN1cnJlbnRseSB3b3JraW5nIG9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc3VyZmFjZSBoZSB3aWxsIGJlIHdvcmtpbmcgb24gaXMgYSBodWdlIHBpZWNlIG9mIHBhcGVyIG1vZGVsZWQgYnkgYSBjb29yZGluYXRlIHBsYW5lLCBvbiB3aGljaCBhbGwgcG9pbnRzIHdpdGggaW50ZWdlciBjb29yZGluYXRlcyBhcmUgbWFya2VkLiBNaXJrbywgSnIuIGRyYXdzIHRoZSBmbG9vciBwbGFuIGJ5IHB1dHRpbmcgaGlzIHBlbmNpbCBpbiB0aGUgb3JpZ2luIGFuZCBtYWtpbmcgTiBmYXN0IGFuZCBjbHVtc3kgc3Ryb2tlcy4gSW4gZWFjaCBzdHJva2UsIGhlIG1vdmVzIHRoZSBwZW5jaWwgKHdpdGhvdXQgbGlmdGluZyBpdCBvZmYgdGhlIHN1cmZhY2UpIHN0cmFpZ2h0IHRvIG9uZSBvZiB0aGUgOCBuZWlnaGJvdXJpbmcgcG9pbnRzIChob3Jpem9udGFsbHksIHZlcnRpY2FsbHkgb3IgZGlhZ29uYWxseSkuIFRoZSBwb3NzaWJsZSBzdHJva2VzIGFyZSBudW1iZXJlZCAwIHRvIDcgYXMgc2hvd24gaW4gdGhlIGltYWdlIGJlbG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FyYzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE5cHg7IG9wYWNpdHk6MC45OyB3aWR0aDoyMTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BZnRlciBzZXZlcmFsIHRob3VzYW5kIHN0cm9rZXMsIE1pcmtvLCBKci4gZmluYWxseSBnZXRzIHRpcmVkIGFmdGVyIHdoaWNoIGhpcyBmYXRoZXIgYXR0ZW1wdHMgdG8gY291bnQgdGhlIG51bWJlciBvZiByb29tcyBpbiB0aGUgZmxvb3IgcGxhbi4gQSByb29tIGlzIGFuIGVtcHR5IHNwYWNlIGluIHRoZSBmbG9vciBwbGFuLCBzdXJyb3VuZGVkIGJ5IHBlbmNpbCBzdHJva2VzIG9uIGFsbCBzaWRlcy4gTm90ZSB0aGF0IGl0IGlzIHBvc3NpYmxlIGZvciByb29tcyB0byBoYXZlICZxdW90O2hvbGVzJnF1b3Q7IGkuZS4gdG8gY29tcGxldGVseSBzdXJyb3VuZCBvdGhlciByb29tcy4gQWxzbywgaXQgaXMgcG9zc2libGUgZm9yIHRoYXQgTWlya28sIEpyLiBkcmF3cyB0aGUgc2FtZSB3YWxsIHNlZ21lbnQgbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgZXhhY3QgcGVuY2lsIHN0cm9rZXMsIGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiByb29tcyBpbiB0aGUgZmxvb3IgcGxhbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApLCB0aGUgbnVtYmVyIG9mIHBlbmNpbCBzdHJva2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgTiBkaWdpdHMgYmV0d2VlbiAwIGFuZCA3LCB0aGUgcGVuY2lsIHN0cm9rZXMgaW4gb3JkZXIgaW4gd2hpY2ggTWlya28sIEpyLiBtYWtlcyB0aGVtLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHJvb21zIGluIHRoZSBmbG9vciBwbGFuLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FyYzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI1cHg7IHdpZHRoOjIyNnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=