You are developing the habit of "Safe Programming." You are given N unsigned integer data types of sizes (in bits) a₁, a₂, a₃, ... , a_n. If the i^th datatype has size a_i bits, you can store all integers from 0 to 2^a_i -1.

The rule of safe programming is as follows:

• If n is a number that can be represented by the bit size a_i, and if at least one a_j > a_i is present in the given array, then we must be able to represent n³ by any one of the bit sizes given in array a.

Task

Output 1 if it is "Safe Programming", else output 0.

Example

Assumptions

• N = 3
• A = [4, 3, 7]

Approach

The given bit sizes are 4, 3, and 7 bits.
Take n = 7. n can be represented by the data type of size a₂ = 3 bits. { 2³-1 = 7}
Here a₁ = 4 and a₃ = 7 are present in the given array such that a₁ > a₂ and a₃ > a₂.
So, according to the rule, we must be able to represent n³ = 343 using the given bit sizes i.e. 4 and 7 bits.
The maximum number that can be represented by the given sizes of bits is 2^a₃ - 1 = 2⁷ - 1 = 127.
Clearly, 343 > 127. Hence we fail to represent 343 from the given bit sizes.
Hence answer will be 0.

Function description

Complete the SafeProgramming() function, which takes the following arguments, and returns true if it is safe programming, otherwise, returns false:

• N: Represents the number of available variations of bit sizes
• a[ ]: Represents the array of Available variations of bit sizes

Input format

• The first line contains N denoting the number of available variations of bit sizes
• The second line contains N space-separated integers denoting the available bit sizes.

Output Format

Output 1 if it is safe programming; else, output 0.

Constraints

\(2 \le N \le 1e6\)

\(3 \le a[i] \le 1e7\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.