시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 146 33 30 28.037%

문제

현욱은 보물 상자 속에서 국제 소 줄서기 사진 콘테스트의 본선 초대권을 발견했다. 전 세계 낙농인이 주목하는 이 대회의 우승자는 첫 대회부터 한 번도 거르지 않고 무려 20년 연속으로 USACO Farm의 존이라는 농부가 차지했는데, 한국인 최초로 우승자가 되고 싶은 현욱은 이참에 키우고 있는 소들로 멋진 사진을 찍어 참가해보기로 했다.

이 대회의 심사 기준은 정확히 알려져 있진 않지만, 소문에 의하면 사진에 찍힌 암소와 수소의 수가 반드시 같아야 하고, 사진에 찍힌 소의 수가 많을수록 높은 점수를 받는다고 한다. 현욱은 키우고 있는 소 중 몇 마리를 골라 심사 기준에 맞게 사진을 찍으려고 했지만, 그러면 사진에 찍히지 못한 소들이 실망하기 때문에 모든 소를 찍은 다음 적당히 사진의 좌우를 세로로 잘라서 대회에 응모하려고 한다.

현욱은 사진을 찍는 것만으로도 바빠서, 찍은 사진을 자르는 작업을 당신에게 부탁했다. 즉, 당신은 심사 기준에 맞춰 주어진 사진을 적당히 잘라 암소와 수소의 수가 동일하면서 소의 수가 최대한 많게 만들어야 한다.

소들이 계속 가만히 서 있다면 사진을 찍는 작업이 비교적 쉽겠지만, 소들은 참을성이 부족하기 때문에 줄을 선 채로 가만히 서 있지 않고 가끔씩 서로 인접한 소끼리 위치를 바꾼다. 하지만 동시에 여러 쌍의 소가 위치를 바꾸지는 않는다. 현욱은 소들이 서로 위치를 바꿀 때마다 새로운 사진을 찍는다.

현욱을 도와 처음 소들이 줄을 선 상태와 사진을 찍는 사이 소들이 어떻게 움직였는지 정보가 주어졌을 때, 각각의 사진에 대해 암소와 수소의 수가 동일하면서 소의 수가 가장 많은 연속한 부분 구간의 길이를 계산하는 프로그램을 작성해보자.

입력

첫 줄에 소의 숫자 N, 찍은 사진의 숫자 M이 주어진다.

둘째 줄에 N개의 숫자가 주어진다. 각 수는 모두 0 또는 1이며, 0은 암소, 1은 수소를 뜻한다.

셋째 줄에 M개의 숫자 P1, P2, ..., Pm이 주어진다. 각각의 Pi 값은 Pi번째 소와 Pi + 1 번째 소가 서로 위치를 바꿨다는 의미이다.

출력

첫째 줄에 처음 주어진 소의 상태에서 암소와 수소의 수가 같은 가장 긴 연속 부분 구간의 길이를 출력한다.

둘째 줄부터 M 줄에 걸쳐, 각각 소들이 위치를 바꾸고 난 후 암소와 수소의 수가 같은 가장 긴 연속 부분 구간의 길이를 출력한다. 어떻게 구간을 잘라도 암소와 수소의 수를 같게 만들 수 없는 사진의 경우 0을 출력한다.

제한

  • 1 ≤ N,M ≤ 105
  • 1 P1, P2, ..., P< N

서브태스크 1 (3점)

  • 1 ≤ N ≤ 100, 1 ≤ M ≤ 6000

서브태스크 2 (3점)

  • 1 ≤ N ≤ 6000, 1 ≤ M ≤ 10000

서브태스크 3 (4점)

  • 추가 제한 없음

예제 입력 1

5 3
0 1 1 1 0
4 3 2

예제 출력 1

2
4
4
4

출처

Contest > 소프트콘 > 제2회 소프트콘 D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.