페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8051

멜론 수박 호박 1s 1024MB

문제

정올이네 가게에서는 오직 멜론, 수박, 호박만을 판매하고 있다.

멜론은 1 kg, 수박은 2 kg, 호박은 3 kg으로 같은 종류의 물건에 대해서는 무게가 언제나 동일하다.

N명의 손님이 찾아와 정올이에게 각각 P_i kg만큼 물건을 사고싶다고했다.

정올이가 손님에게 줄 수 있는 물건의 조합은 총 몇가지인지 알아보자.

P=4의 경우 아래와 같이 네 가지 경우가 가능하다.

  • 멜론 4개

  • 호박 1개, 멜론 1개

  • 수박 2개

  • 멜론 2개, 수박 1개


입력

첫 줄에 정수 N이 주어진다.

두 번째 줄에 P_1, P_2, ..., P_N이 주어진다.

  • 1 \le N \le 100,000

  • 1 \le P_i \le 10,000 (1 \le i \le N)


출력

첫 줄에 각 손님의 주문에 대하여 가능한 경우의 수를 공백으로 구분하여 출력한다.


예제 

3
4 10 20
4 14 44


출처

klee

로그인해야 코드를 작성할 수 있어요.