시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 356 91 57 26.512%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

19
6664442220001655360

예제 출력 1

3

힌트

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

W3sicHJvYmxlbV9pZCI6IjMxMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYzlcdWJhNzRcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVjMGI0IFx1YzlkMVx1Yzc0NCBcdWMxMjRcdWFjYzRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWNcdWI5YzhcdWIyZTQgXHVjODEwXHVjNzc0IFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3MCBcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWM3NzQgXHVjODg1XHVjNzc0XHVjNzU4IFx1YzZkMFx1YzgxMFx1YzVkMCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVjNjJjXHViOWIwXHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YmU2MFx1Yjk3NFx1YWM4YyBOXHViYzg4IFx1YzZjMFx1YzljMVx1YzVlYyBcdWQzYzlcdWJhNzRcdWIzYzRcdWI5N2MgXHVhZGY4XHViOWIwXHViMmU0LiBcdWM1ZjBcdWQ1NDRcdWM3NDAgXHVjODA4XHViMzAwXHViODVjIFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YzExYyBcdWI1YmNcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIDhcdWFjMWMgXHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwKSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzc0XHViM2Q5XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzNjXHViYTcwLCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYXJjMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgd2lkdGg6MjE5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWRmOFx1YjliMCBcdWQzYzlcdWJhNzRcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmMyOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmMyOVx1Yzc0MCBcdWQzYzlcdWJhNzRcdWIzYzQgXHVjMGMxXHVjNWQwXHVjMTFjIFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NzRcdWJhNzAsIFx1YzVmMFx1ZDU0NCBcdWMxMjBcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1YmE3NFx1Yzc3NCBcdWI0NThcdWI3ZWMgXHVjMzEzXHVjNWVjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmMyOVx1Yzc0MCBcdWIyZTRcdWI5NzggXHViYzI5XHVjNzNjXHViODVjIFx1YjQ1OFx1YjdlYyBcdWMzMTNcdWM1ZWNcdWM5YzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWFkZjhcdWM1YzhcdWIzNTggXHVjMTIwXHVjNzQ0IFx1YjYxMCBcdWFkZjhcdWI5YjQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWQ2OWZcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YmE3MCAwXHViZDgwXHVkMTMwIDdcdWFlNGNcdWM5YzBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1ZDNjOVx1YmE3NFx1YjNjNFx1Yzc1OCBcdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9hcmMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyNXB4OyB3aWR0aDoyMjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWM4MWNcdWI5N2MgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YWRmOFx1YjlhY1x1YmE3NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHViMmU0PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQVJISVRFS1QiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBhcmNoaXRlY3QgTWlya28gaGFzIGdpdmVuIGhpcyB0aHJlZS15ZWFyIG9sZCBzb24sIE1pcmtvLCBKci4sIHRoZSB0YXNrIG9mIGNyZWF0aW5nIHRoZSBmbG9vciBwbGFuIGZvciB0aGUgYnVpbGRpbmcgaGUgaXMgY3VycmVudGx5IHdvcmtpbmcgb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzdXJmYWNlIGhlIHdpbGwgYmUgd29ya2luZyBvbiBpcyBhIGh1Z2UgcGllY2Ugb2YgcGFwZXIgbW9kZWxlZCBieSBhIGNvb3JkaW5hdGUgcGxhbmUsIG9uIHdoaWNoIGFsbCBwb2ludHMgd2l0aCBpbnRlZ2VyIGNvb3JkaW5hdGVzIGFyZSBtYXJrZWQuIE1pcmtvLCBKci4gZHJhd3MgdGhlIGZsb29yIHBsYW4gYnkgcHV0dGluZyBoaXMgcGVuY2lsIGluIHRoZSBvcmlnaW4gYW5kIG1ha2luZyBOIGZhc3QgYW5kIGNsdW1zeSBzdHJva2VzLiBJbiBlYWNoIHN0cm9rZSwgaGUgbW92ZXMgdGhlIHBlbmNpbCAod2l0aG91dCBsaWZ0aW5nIGl0IG9mZiB0aGUgc3VyZmFjZSkgc3RyYWlnaHQgdG8gb25lIG9mIHRoZSA4IG5laWdoYm91cmluZyBwb2ludHMgKGhvcml6b250YWxseSwgdmVydGljYWxseSBvciBkaWFnb25hbGx5KS4gVGhlIHBvc3NpYmxlIHN0cm9rZXMgYXJlIG51bWJlcmVkIDAgdG8gNyBhcyBzaG93biBpbiB0aGUgaW1hZ2UgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYXJjMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgb3BhY2l0eTowLjk7IHdpZHRoOjIxOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFmdGVyIHNldmVyYWwgdGhvdXNhbmQgc3Ryb2tlcywgTWlya28sIEpyLiBmaW5hbGx5IGdldHMgdGlyZWQgYWZ0ZXIgd2hpY2ggaGlzIGZhdGhlciBhdHRlbXB0cyB0byBjb3VudCB0aGUgbnVtYmVyIG9mIHJvb21zIGluIHRoZSBmbG9vciBwbGFuLiBBIHJvb20gaXMgYW4gZW1wdHkgc3BhY2UgaW4gdGhlIGZsb29yIHBsYW4sIHN1cnJvdW5kZWQgYnkgcGVuY2lsIHN0cm9rZXMgb24gYWxsIHNpZGVzLiBOb3RlIHRoYXQgaXQgaXMgcG9zc2libGUgZm9yIHJvb21zIHRvIGhhdmUgJnF1b3Q7aG9sZXMmcXVvdDsgaS5lLiB0byBjb21wbGV0ZWx5IHN1cnJvdW5kIG90aGVyIHJvb21zLiBBbHNvLCBpdCBpcyBwb3NzaWJsZSBmb3IgdGhhdCBNaXJrbywgSnIuIGRyYXdzIHRoZSBzYW1lIHdhbGwgc2VnbWVudCBtb3JlIHRoYW4gb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBleGFjdCBwZW5jaWwgc3Ryb2tlcywgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHJvb21zIGluIHRoZSBmbG9vciBwbGFuLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgcGVuY2lsIHN0cm9rZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyBvZiBOIGRpZ2l0cyBiZXR3ZWVuIDAgYW5kIDcsIHRoZSBwZW5jaWwgc3Ryb2tlcyBpbiBvcmRlciBpbiB3aGljaCBNaXJrbywgSnIuIG1ha2VzIHRoZW0uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygcm9vbXMgaW4gdGhlIGZsb29yIHBsYW4uPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYXJjMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjVweDsgd2lkdGg6MjI2cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==