시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2521019446.078%

문제

서울과학고의 급식실은 줄이 깁니다. 은호는 줄을 선 사람들 중 연속한 위치에 있는 몇 명을 골라 인터뷰를 하려고 합니다. 단, 은호와 같은 학년의 학생은 인터뷰를 할 수 없습니다.

현재 급식실에는 $N$명의 학생이 줄을 서 있습니다. 은호는 문득 자신이 인터뷰를 할 수 있는 방법이 몇 가지나 될지 궁금해졌습니다. 다음과 같은 $Q$개의 질문에 답해 은호의 궁금증을 풀어 줍시다.

  • 앞 $X_i$명의 학생들 중 연속한 몇 명을 골라 인터뷰를 할 때, 자신과 같은 학년의 학생이 한 명도 없도록 고르는 방법의 수는 몇 가지인가?

입력

첫 줄에 학생의 수 $N$과 은호의 학년을 나타내는 정수 $K$, 그리고 질문의 수 $Q$가 주어집니다. 둘째 줄에 줄을 서 있는 학생들의 학년 $A_1$, $A_2$, $\cdots$, $A_N$이 띄어쓰기를 사이에 두고 주어집니다. $i$번 학생은 앞에서부터 $i$번째에 서 있는 학생을 말합니다. 셋째 줄에 $Q$개의 질문에 대한 정수 $X_1$, $X_2$, $\cdots$, $X_Q$가 띄어쓰기를 사이에 두고 주어집니다.

출력

각 경우에 대해 가능한 인터뷰 대상의 가짓수를 한 줄에 하나씩 출력합니다.

제한

  • $1 \le N \le 10^5$
  • $1 \le K \le 3$
  • $1 \le Q \le N$
  • $1 \le A_i \le 3$ ($1 \le i \le N$)
  • $1 \le X_1 < \cdots < X_Q \le N$

서브태스크

번호배점제한
111

$N \le 10$, $Q=1$, $X_1 = N$

223

$N \le 4000$, $Q=1$, $X_1 = N$

329

$N \le 4000$, $Q \le 4000$

437

추가 제한 조건이 없다.

예제 입력 1

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

예제 출력 1

1
1
2
4
4

예제 1에서, 전체 구간 내에서 가능한 인터뷰 구간은 [1, 1], [3, 3], [3, 4], [4, 4]의 네 가지입니다.

출처

High School > 서울과학고등학교 > 2023 SciCom Qualification Test B번

채점 및 기타 정보

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