시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 4 3 30.000%

문제

총 N개의 양의 정수로 이루어진 수열 B = B0, ..., BN-1가 주어진다. 이 때, 아래와 같은 성질을 만족하는 수열 A = A0, ..., AN-1을 만드려고 한다.

  • 수열 A의 모든 수는 서로 달라야 한다.
  • 모든 Ai는 1보다 커야 한다.
  • 모든 i에 대해서, Ai^Bi (Ai의 Bi제곱)은 Pi로 나누어 떨어져야 한다. 이 때, Pi는 A에서 Ai를 제외한 수를 모두 곱한 값이다. 즉, Pi = A0×A1×...×Ai-1×Ai+1×...×AN-1 이다.

수열 A를 만들 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (2 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 수열 B가 주어진다. (1 ≤ Bi ≤ 10)

출력

첫째 줄에 수열 A를 만들 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1

2
2 1

예제 출력 1

1

예제 입력 2

2
1 1

예제 출력 2

0

예제 입력 3

3
7 7 7

예제 출력 3

1

출처