만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

인터뷰

면접 대비

시간 제한1초메모리 제한1024 MB

요약
은호와 같은 학년이 없는 연속된 학생 묶음의 수를 앞에서 X명 범위 안에서 각 질의마다 구합니다.
난이도

쉬움10점 중 3점

유형
배열, 누적 합, 수학
정답자
아직 제출이 없습니다

문제

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

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

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

입력

첫 줄에 학생의 수 NN, 은호의 학년 KK, 질문의 수 QQ가 띄어쓰기를 사이에 두고 주어집니다. 둘째 줄에는 줄을 서 있는 학생들의 학년 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 띄어쓰기를 사이에 두고 주어집니다. ii번 학생은 앞에서부터 ii번째에 서 있는 학생을 말합니다. 셋째 줄에는 QQ개의 질문에 대한 정수 X1,X2,⋯ ,XQX_1, X_2, \cdots, X_Q가 띄어쓰기를 사이에 두고 주어집니다.

출력

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

제한

  • 1≤N≤1051 \le N \le 10^5
  • 1≤K≤31 \le K \le 3
  • 1≤Q≤N1 \le Q \le N
  • 1≤Ai≤31 \le A_i \le 3 (1≤i≤N1 \le i \le N)
  • 1≤X1<⋯<XQ≤N1 \le X_1 < \cdots < X_Q \le N

예제1

  1. 예제 1

    입력
    5 2 5
1 2 3 1 2
1 2 3 4 5
    예상 출력
    1
1
2
4
4