시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB29117514863.248%

문제

우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의 농장을 방문한 것이었다. 그 사이에 우리가 도와주려고 했던 존은 자신의 코드를 아무리 디버깅을 해 봐도 틀렸습니다나 런타임 에러가 나서 포기하고 제2안을 시도하고 있다.

존은 최근에 일부 종은 친하다는 것을 알게 되었다. 존의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.

존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명할 것이다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.

그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.

입력

첫 줄에 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.

예제 입력 1

6
1
2
3
4
5
6
6
5
4
3
2
1

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjE0NDU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDExIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2YjBcdWI5YWNcdWIyOTQgPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzE0NDU4XCI+XHVjODc0XHVjNzU4IFx1YWNlMFx1YmJmYzxcL2E+XHVjNzQ0IFx1ZDU3NFx1YWNiMFx1ZDU3NCBcdWM5MDQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YzljMFx1YjljYywgXHVhZGY4XHVhYzc4IFx1YzU0Y1x1YjgyNCBcdWM4ZmNcdWI3ZWMgXHVhYzAwXHViMmU0XHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWM3ODNcdWM1YzhcdWIyZTQuIFx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVhYzAwXHVhZTM0IFx1ZDU4OFx1YzljMFx1YjljYywgMk5cdWFjMWNcdWM3NTggXHViYWE5XHVjZDA4XHVjOWMwXHViMjk0IFx1YzVjNlx1YWNlMCBcdWM2ZWMgPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzE0NDY2XCI+TiZ0aW1lcztOIFx1YWNhOVx1Yzc5MDxcL2E+XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzU0Y1x1YWNlMCBcdWJjZjRcdWIyYzggXHVjNmIwXHViOWFjXHViMjk0IFx1YjNkOVx1YmE4NVx1Yzc3NFx1Yzc3OFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM3NDQgXHViYzI5XHViYjM4XHVkNTVjIFx1YWM4M1x1Yzc3NFx1YzVjOFx1YjJlNC4gXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM2YjBcdWI5YWNcdWFjMDAgXHViM2M0XHVjNjQwXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU4OFx1YjM1OCBcdWM4NzRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWM1NDRcdWJiMzRcdWI5YWMgXHViNTE0XHViYzg0XHVhZTQ1XHVjNzQ0IFx1ZDU3NCBcdWJkMTBcdWIzYzQgXHVkMmMwXHViODM4XHVjMmI1XHViMmM4XHViMmU0XHViMDk4IFx1YjdmMFx1ZDBjMFx1Yzc4NCBcdWM1ZDBcdWI3ZWNcdWFjMDAgXHViMDk4XHVjMTFjIFx1ZDNlY1x1YWUzMFx1ZDU1OFx1YWNlMCBcdWM4MWMyXHVjNTQ4XHVjNzQ0IFx1YzJkY1x1YjNjNFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc0MCBcdWNkNWNcdWFkZmNcdWM1ZDAgXHVjNzdjXHViZDgwIFx1Yzg4NVx1Yzc0MCBcdWNlNWNcdWQ1NThcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDBcdWIyOTQgTiBcdWM4ODVcdWI5NThcdWM3NTggXHVjMThjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxIDFcdWJjODggXHVjODg1LCAyXHViYzg4IFx1Yzg4NSwgLi4uLCBOXHViYzg4IFx1Yzg4NVx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIHxhJm1pbnVzO2J8ICZsZTsgNFx1Yjc3Y1x1YmE3NCBhXHViYzg4IFx1Yzg4NVx1YWNmYyBiXHViYzg4IFx1Yzg4NVx1Yzc1OCBcdWMxOGNcdWIyOTQgXHVjZTVjXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWIwOThcdWMwNThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWFlMzAgXHVkNjExXHVkNjhjXHVjNWQwIFx1YzBjOFx1Yjg1YyBcdWFjMDBcdWM3ODVcdWQ1NWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWIxOGRcdWM3YTVcdWM3NTggXHVhZDZjXHVjODcwXHViOTdjIFx1YjJlNFx1YzJkYyBcdWMxMjRcdWJhODVcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIxOGRcdWM3YTVcdWM1ZDBcdWIyOTQgXHVjNzdjXHVjNzkwXHVkNjE1IFx1YWUzOFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzU5MVx1Y2FiZFx1YzVkMCBcdWJhYTlcdWNkMDhcdWM5YzBcdWFjMDAgTlx1YWMxY1x1YzUyOSBcdWM3ODhcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWJhYTlcdWNkMDhcdWM5YzBcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMxOGNcdWFjMDAgXHVkNTVjIFx1YmFhOVx1Y2QwOFx1YzljMFx1YzUyOSBcdWNjMjhcdWM5YzBcdWQ1NThcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWIzYzQgXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LiBcdWFkNTBcdWQxYjVcdWMwYWNcdWFjZTBcdWI5N2MgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4NzRcdWM3NDAgXHVkNmExXHViMmU4XHViY2Y0XHViM2M0XHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWIyOTQgXHVjNjdjXHVjYWJkXHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFlMzhcdWM1ZDAgXHVjMjE4XHVjOWMxXHVjNzdjIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWMwYWNcdWM3NzRcdWFjMDAgXHVjODhiXHVjNzQwIFx1YzE4Y1x1YjRlNFx1YjA3Y1x1YjlhYyBcdWM1ZjBcdWFjYjBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1ZDZhMVx1YjJlOFx1YmNmNFx1YjNjNFx1YjljYyBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVkNmExXHViMmU4XHViY2Y0XHViM2M0XHVhYzAwIFx1YWNiOVx1Y2U1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWM3NTggXHViMThkXHVjN2E1XHVjNzQ0IFx1YjQ1OFx1YjdlY1x1YmNmNFx1YmE3NFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YjljZVx1Yzc3NCBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTc0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwXHViY2M0XHViODVjIFx1YzE4Y1x1Yzc1OCBcdWM4ODUgXHViYzg4XHVkNjM4XHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4ODVcdWM3NDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWNkMDhcdWM5YzBcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTQ0NTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaHkgRGlkIHRoZSBDb3cgQ3Jvc3MgdGhlIFJvYWQgSUkgKFBsYXRpbnVtKSIsImRlc2NyaXB0aW9uIjoiPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGlzIGNvbnRpbnVpbmcgdG8gcG9uZGVyIHRoZSBpc3N1ZSBvZiBjb3dzIGNyb3NzaW5nIHRoZSByb2FkIHRocm91Z2ggaGlzIGZhcm0sIGludHJvZHVjZWQgaW4gdGhlIHByZWNlZGluZyBwcm9ibGVtLiBIZSByZWFsaXplcyB0aGF0IGludGVyYWN0aW9uIGJldHdlZW4gc29tZSBwYWlycyBvZiBicmVlZHMgaXMgYWN0dWFsbHkgYWNjZXB0YWJsZSBpZiB0aGUgYnJlZWRzIGFyZSBmcmllbmRseSwgYSBwcm9wZXJ0eSB0aGF0IHR1cm5zIG91dCB0byBiZSBlYXNpbHkgY2hhcmFjdGVyaXplZCBpbiB0ZXJtcyBvZiBicmVlZCBJRDogYnJlZWRzJm5ic3A7YSZuYnNwO2FuZCZuYnNwO2ImbmJzcDthcmUgZnJpZW5kbHkgaWYmbmJzcDt8YSZtaW51cztifCAmbGU7IDQsIGFuZCB1bmZyaWVuZGx5IG90aGVyd2lzZS4gSXQgaXMgb2sgZm9yIGNvd3MgdG8gd2FuZGVyIGludG8gZmllbGRzIGRlc2lnbmF0ZWQgZm9yIG90aGVyIGJyZWVkcywgYXMgbG9uZyBhcyB0aGV5IGFyZSBmcmllbmRseS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG9yZGVyaW5nIG9mJm5ic3A7TiZuYnNwO2ZpZWxkcyBvbiBib3RoIHNpZGVzIG9mIHRoZSByb2FkIHRocm91Z2ggRkomIzM5O3MgZmFybSAoYWdhaW4sIHdpdGggZXhhY3RseSBvbmUgZmllbGQgZm9yIGVhY2ggYnJlZWQgb24gZWFjaCBzaWRlKSwgcGxlYXNlIGhlbHAgRkogZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjcm9zc3dhbGtzIGhlIGNhbiBkcmF3IG92ZXIgaGlzIHJvYWQsIHN1Y2ggdGhhdCBubyB0d28gaW50ZXJzZWN0LCBhbmQgc3VjaCB0aGF0IGVhY2ggY3Jvc3N3YWxrIGpvaW5zIGEgcGFpciBvZiBmaWVsZHMgY29udGFpbmluZyB0d28gYnJlZWRzIHRoYXQgYXJlIGZyaWVuZGx5LiBFYWNoIGZpZWxkIGNhbiBiZSBhY2Nlc3NpYmxlIHZpYSBhdCBtb3N0IG9uZSBjcm9zc3dhbGsgKHNvIGNyb3Nzd2Fsa3MgZG9uJiMzOTt0IG1lZXQgYXQgdGhlaXIgZW5kcG9pbnRzKS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyZuYnNwO04mbmJzcDsoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKS4gVGhlIG5leHQmbmJzcDtOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkOyBlYWNoIGJyZWVkIElEIGlzIGFuIGludGVnZXIgaW4gdGhlIHJhbmdlJm5ic3A7MSZoZWxsaXA7Ti4gVGhlIGxhc3QmbmJzcDtOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgdGhlIGZpZWxkcyBvbiB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgcm9hZC4gRWFjaCBicmVlZCBJRCBhcHBlYXJzIGV4YWN0bHkgb25jZSBpbiBlYWNoIG9yZGVyaW5nLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGRpc2pvaW50ICZxdW90O2ZyaWVuZGx5IGNyb3Nzd2Fsa3MmcXVvdDsgRmFybWVyIEpvaG4gY2FuIGRyYXcgYWNyb3NzIHRoZSByb2FkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Platinum 2번

  • 문제를 번역한 사람: jh05013