Mai nhận được rất nhiều bánh kem trong ngày sinh nhật nên phải xếp chồng bánh lên nhau để đủ chỗ. Vì bánh rất mềm nên mỗi chồng có tối đa 2 chiếc, và chiếc đặt ở trên phải có trọng lượng không quá một nửa trọng lượng của chiếc đặt ở dưới. Cũng có thể có những chồng chỉ gồm một chiếc bánh.

Ví dụ: có 8 chiếc bánh với trọng lượng lần lượt là 2, 5, 7, 6, 9, 8, 4, 2. Một cách xếp thành 5 chồng là: {5}, {7 ở dưới, 2 ở trên}, {6 ở dưới, 2 ở trên}, {9}, {8 ở dưới, 4 ở trên}.

Cho ~n~ chiếc bánh với trọng lượng cho trước, hãy tìm số chồng bánh ít nhất mà Mai có thể xếp được (mọi chiếc bánh đều phải được xếp vào một chồng).

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~) là số chiếc bánh.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) là trọng lượng các chiếc bánh.

Kết quả

Ghi ra một số nguyên dương duy nhất là số chồng bánh ít nhất.

Ví dụ

CAKES.INP

8
2 5 7 6 9 8 4 2

CAKES.OUT

5

Giải thích: cách xếp {5}, {7,2}, {6,2}, {9}, {8,4} cho 5 chồng, và không thể ít hơn.

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 1000~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.