시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 302 130 123 46.067%

문제

예선에서 예고했던 쿼리 문제를 출제하려고 했지만 『진짜』 쿼리 문제를 내면 대회가 너무 어려워지기 때문에 쿼리 대신 스테판 쿼리가 등장했다!

스테판 쿼리는 등번호 30번! 조선의 가위바위보 선수이다. 오늘은 제1회 천하제일 운빨대회가 열리는 날이다. 쿼리가 속한 『남자는 불꽃 주먹 에이스』 팀과 서구의 전통강호인 『뉴욕동 보자기 다니엘삿갓』 팀이 이번 결승에서 맞붙게 되었다. 또한 이번 경기의 결과에 따라, 가장 많은 연승을 챙긴 선수는 상금과 함께 ‘상금으로 챙겨드려 어머니 생일 상’이라는 명예로운 타이틀을 거머쥐게 된다.

게임은 다음과 같이 진행된다. 양 팀의 인원수에는 관계없이 총 N 라운드를 진행한다. 게임은 진 사람이 탈락하고 이긴 사람이 게임을 계속하는 서바이벌 형태로 진행된다. (단, 비긴 경우에는 새로 출전한 사람이 승리한 것으로 간주하며, 첫 판에는 비기는 경우 없이 반드시 승패가 갈린다) 편의상 가위를 1, 바위를 2, 보를 3이라고 하자. 과연 가장 많은 승리를 거머쥐고 ‘상금으로 챙겨드려 어머니 생일 상’을 받게 될 선수는 몇 연승을 거둘 수 있을까?

입력

첫째 줄에 라운드의 수 N이 주어진다. (1 <= N <= 300) 둘째 줄에 『남자는 불꽃 주먹 에이스』 팀의 i번째 라운드 가위바위보 정보가, 셋째 줄에 『뉴욕동 보자기 다니엘삿갓』 팀의 i번째 라운드 가위바위보가 정보가 각각 N개씩 주어진다.

출력

가장 많은 연승을 한 선수의 연승 횟수를 출력한다.

예제 입력 1

4
1 2 3 1
2 1 3 1

예제 출력 1

1

예제 입력 2

5
2 3 1 3 1
1 1 2 3 2

예제 출력 2

2