Lập trình an toàn

Trong một nhiệm vụ cứu hộ khẩn cấp, FullHouse Dev được giao nhiệm vụ phát triển một hệ thống phần mềm quan trọng. Để đảm bảo an toàn tối đa, họ quyết định áp dụng nguyên tắc "Lập trình an toàn". Nhiệm vụ này đòi hỏi họ phải xử lý dữ liệu một cách cẩn thận và chính xác để hỗ trợ công tác cứu hộ hiệu quả.

Bài toán

FullHouse Dev được cung cấp \(N\) kiểu dữ liệu số nguyên không dấu với kích thước (tính bằng bit) \(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ữ tất cả các số nguyên 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 có ít nhất một \(a_j > a_i\) trong mảng đã cho, thì chúng ta phải có thể biểu diễn \(n^3\) bằng bất kỳ một trong các kích thước bit nào trong mảng \(a\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) biểu thị số lượng biến thể kích thước bit có sẵn.
• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi khoảng trắng biểu thị 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 64\)

VÍ DỤ

INPUT

4
3 10 3 3

OUTPUT

1

Giải thích

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

Cách tiếp cận:

• Các kích thước bit cho là 3, 10, 3 và 3.
• Lấy \(n = 7\). Nó có thể được 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\) có trong mảng đã cho và \(a_2 > a_1\).
• Theo quy tắc, chúng ta phải có thể biểu diễn \(n^3 = 343\) bằng kích thước bit đã cho, tức là 10 bit.
• Số lớn nhất có thể biểu diễn bằng 10 bit là \(2^{a_2} - 1 = 2^{10} - 1 = 1023\).
• Rõ ràng, \(343 < 1023\). Do đó, chúng ta có thể biểu diễn 343 từ các kích thước bit đã cho.

Vì vậy, đáp án là 1, biểu thị rằng đây là một trường hợp "Lập trình an toàn".