Lập trình an toàn

Trong một buổi thảo luận về an ninh mạng, FullHouse Dev được giao nhiệm vụ phát triển một hệ thống kiểm tra tính an toàn của việc lưu trữ dữ liệu. Họ cần xây dựng một chương trình để đảm bảo việc biểu diễn số nguyên và các phép toán trên số nguyên không bị tràn bộ nhớ.

Bài toán

Cho \(N\) kiểu dữ liệu số nguyên không dấu có kích thước (tính bằng bit) là \(a_1\), \(a_2\), \(a_3\), ..., \(a_n\). Nếu kiểu dữ liệu thứ \(i\) có kích thước \(a_i\) bit, nó có thể lưu trữ các số từ 0 đến \(2^{a_i} - 1\).

Quy tắc lập trình an toàn như sau:

Nếu \(n\) là một số có thể biểu diễn bởi kích thước bit \(a_i\), và nếu tồn tại ít nhất một \(a_j > a_i\) trong mảng đã cho, thì \(n^3\) phải có thể biểu diễn được bởi một trong các kích thước bit trong mảng \(a\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số lượng biến thể kích thước bit.

• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách - các kích thước bit có sẵn.

OUTPUT FORMAT:

• In ra 1 nếu đó là lập trình an toàn, ngược lại in ra 0.

Ràng buộc:

• \(1 \leq N \leq 10^5\)

• \(1 \leq a_i \leq 32\)

Ví dụ

INPUT

4
3 10 3 3

OUTPUT

1

Giải thích

Cho:

• \(N = 4\)
• \(a = [3, 10, 3, 3]\)

Phân tích:

• Các kích thước bit cho trước là 3, 10, 3 và 3.
• Lấy \(n = 7\), số này có thể biểu diễn bởi kiểu dữ liệu có kích thước \(a_1 = 3\) bit (\(2^3 - 1 = 7\)).
• Ở đây \(a_2 = 10\) tồn tại trong mảng và \(a_2 > a_1\).
• Theo quy tắc, ta phải có thể biểu diễn \(n^3 = 343\) bằng các kích thước bit cho trước, cụ thể là 10 bit.
• Số lớn nhất có thể biểu diễn bằng 10 bit là \(2^{10} - 1 = 1023\).
• Do \(343 < 1023\) nên ta có thể biểu diễn 343 bằng các kích thước bit cho trước.
• Vì vậy kết quả là 1.