Số ước nhiều nhất

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho số nguyên dương ~n~ và dãy số nguyên dương gồm ~n~ phần tử ~a_1,a_2,…,a_n~.

Yêu cầu: Hãy đưa ra số lượng ước dương của một phần tử có nhiều ước dương nhất trong dãy số đã cho.

Input

  • Dòng 1 chứa số nguyên dương ~n~ (~1≤n≤10^5~).
  • Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử từ ~a_1,a_2,…,a_n~ (~1≤a_i≤10^6~)

Output

Ghi ra một số nguyên là kết quả bài toán — số lượng ước dương lớn nhất của một phần tử trong dãy số.

Scoring

  • Có 70% số test ứng với 70% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^3~;
  • Có 15% số test ứng với 15% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^6~;
  • Có 15% số test còn lại ứng với 15% số điểm không có ràng buộc gì thêm.

Examples

Input

4
3 8 16 22

Output

5

Input

5
3 5 6 17 8

Output

4

Note

  • Phần tử 16 có nhiều ước dương nhất là 1,2,4,8,16 (tổng cộng 5 ước).

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.