# PROBLEM LINK:

Practice

Contest : Click here

* Author:* arnie8991

*horsbug98*

**Tester:***arnie8991*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

# EXPLANATION:

The best approach to solve this problem quickly is to use the rabin miller primalty test to check which numbers are prime and then keep the count.

You can read more about the Rabin Miller algorithm for primalty check and other similar algorithms from here.

We have to individually count how many primes are there in the first half and the second half of the array and then decide whether the conditions are met or not.

# SOLUTIONS:

## Setter's Solution

```
def check_composite(n, a, d, s):
x = pow(a, d, n)
if x==1 or x==n-1:
return False
for r in range(1, s):
x = x * x % n
if x==n-1:
return False
return True
def miller_rabin(n):
if n<2:
return 0
r = 0
d = n-1
while((d&1)==0):
d >>=1
r += 1
base = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in base:
if n==a:
return 1
if check_composite(n, a, d, r):
return 0
return 1
n = int(input())
input_array = [int(x) for x in input().split()]
first_prime = -2
last_prime = -2
leftCount = 0
rightCount = 0
for i in range(n//2):
if (miller_rabin(input_array[i]) == 1):
if first_prime == -2:
first_prime = input_array[i]
leftCount+=1
for i in range(n//2,n):
if (miller_rabin(input_array[i]) == 1):
last_prime = input_array[i]
rightCount+=1
if (leftCount == rightCount and first_prime>last_prime):
print('PERFECT')
else:
print('IMPERFECT')
```