#357 I Hate Orbital

Loading problem...

Preparing the statement, recent submissions, and submit form.

#357 I Hate Orbital | DOJ

Statement

양의 정수 $x$ 가 어떤 양의 정수 $k$ 에 대해 $x=2k^2$ 를 만족하면, $x$ 를 오비수라고 하자.

양의 정수로 이루어진 길이 $N$ 의 수열 $A_1,A_2,\cdots,A_N$ 이 주어진다. 수열이 다음 조건 중 하나라도 만족하면 불안정한 수열이라고 한다.

주어진 수열에서 원소를 몇 개 지워 불안정한 수열이 아니게 만들고자 한다. 지워야 하는 원소 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

첫째 줄에 지워야 하는 원소 개수의 최솟값을 출력한다.

Sample 1

Input

5
3 6 8 11 21

Output

Sample 2

Input

10
3 3 3 6 6 5 10 10 18 18

Output

Sample 3

Input

12
3 12 12 6 24 24 24 7 14 5 20 45

Output