Câu chuyện cổ tích về người cha và bó đũa nhắc nhở chúng ta rằng: có đoàn kết thì mới có sức mạnh.

Bạn có \(N\) bó đũa trên một hàng ngang, bó đũa thứ \(i\) có sức mạnh là \(A_i\). Tại mỗi bước, bạn có thể buộc hai bó đũa nằm cạnh nhau và có sức mạnh giống nhau để tạo thành một bó đũa có sức mạnh mới lớn hơn 1 đơn vị so với ban đầu. Bó đũa mới chiếm vị trí của hai bó đũa cũ, và thứ tự của các bó đũa được giữ nguyên.

Để thể hiện tinh thần đoàn kết ở mức cao nhất, bạn muốn lặp lại thao tác trên nhiều lần nhất có thể. Nói cách khác, bạn muốn số lượng bó đũa còn lại là tối thiểu.

Yêu cầu: Hãy viết chương trình tính số lượng bó đũa còn lại tối thiểu có thể đạt được.

Input

• Dòng đầu chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), số lượng bó đũa ban đầu.
• Dòng tiếp theo chứa \(N\) số nguyên, số nguyên thứ \(i\) là \(A_i\) cho biết sức mạnh ban đầu của bó đũa thứ \(i\) \((1 \leq A_i \leq 10^9)\).

Output

• Ghi ra một số nguyên duy nhất là số bó đũa tối thiểu có thể đạt được.

Example

6
1 1 2 2 2 1

2

5
1 1 1 2 1

3

Scoring

• \(30\%\) số điểm của bài tương ứng với các test có \(N \leq 400\).
• \(30\%\) số điểm khác của bài tương ứng với các test có \(A_i \leq 20\).