Sleep Sort is a sorting method described below:

 let A = array to be sorted
 let q = thread-safe queue
 for each v in A :
     create a new thread executing :
         sleep(v seconds)
         q.push(v)

DK's computer is extremely high-tech so that
1. the time of sleeping is absolutely accurate.
2. only the push operation (q.push(v)) and sleep operation executed non-instantly.
3. threads scheduling does not affect this sorting.

DK's magic thread-safe queue has to work on the q.push(v) operation for exact ceil(sqrt(v)) seconds.
During this time other thread which intends to use the queue has to wait for it until it finishes, and then take control of the queue.
When a thread finishes pushing and there are multiple threads waiting, the next one is chosen randomly, which may bring a wrong result.

Given an array A, check whether DK's Sleep Sort may cause a wrong result.

The first line contains an integer n, the length of array A.
The next line contains n integers, representing elements of A.

Output "1" if the sorting will always be correct. Otherwise output "0".

4
1 2 2 5

1

t = 1 v1 = 1 ends sleep and starts to be pushed into queue
t = 2 v2 = 2 and v3 = 2 end sleep and starts to be pushed in to queue, v1 = 1 is already pushed into queue.
t = 4 v2 or v3(for example v2) is already pushed into queue.
t = 5 v4 = 5 ends sleep.
t = 6 v3 = 2 is pushed into queue.
t = 9 v4 = 5 is pushed into queue.

4
4 2 3 2

0