Tèo là một cậu bé rất khỏe nhưng cũng cực kỳ lười biếng. Hôm nay, Tèo được phú ông giao cho nhiệm vụ vào rừng đốn củi. Phú ông đưa cho Tèo một danh sách gồm ~n~ cây của phú ông muốn đốn. Mỗi cây khi đốn sẽ mang lại cho Tèo ~a_i~ bó củi. Những cây nào không đốn thì không được bó củi nào. Nếu Tèo đốn được ít nhất một nửa tổng số bó củi theo yêu cầu trong buổi sáng, thì sẽ được phú ông thưởng cho một bữa cơm trưa no nê.

Ví dụ, nếu có ~3~ cây trong danh sách, tương ứng cho ~1, 3~ và ~4~ bó củi, thì tổng số là ~8~ bó, và chỉ cần đốn đủ ~4~ bó là đủ điều kiện để được thưởng. Tèo rất khỏe mạnh, có thể đốn bất kỳ cây nào mà không gặp khó khăn. Nhưng cậu lại rất lười, nên muốn đốn ít cây nhất có thể để vẫn được bữa cơm trưa ngon lành. Tèo chỉ muốn đốn liền mạch một đoạn cây nào đó trong danh sách. Tức là Tèo chọn một cây số hiệu ~k~, rồi lần lượt đốn các cây số ~k, k+1, k+2, \dots~ cho đến khi vừa đủ số bó củi tối thiểu theo yêu cầu. Tuy nhiên, để giảm bớt công sức, Tèo có thể chọn bỏ qua nhiều nhất một cây trong đoạn đó, nếu việc bỏ cây đó giúp giảm số lượng cây phải đốn mà vẫn đảm bảo đủ chỉ tiêu.

Yêu cầu: Hãy xác định số lượng cây ít nhất mà Tèo cần đốn (theo chiến lược lười biếng của mình) để được phần thưởng từ phú ông.

Input

• Dòng thứ nhất là số nguyên ~n~ (~1 \le n \le 10^5~).

• Dòng tiếp theo ghi các số nguyên ~a_i~ là số bó củi khi đốn được cây thứ ~i~ (~1 \le a_i \le 10^9~).

Output

Một dòng ghi số cây ít nhất mà Tèo cần phải đốn để đạt chỉ tiêu của Phú ông.

Scoring

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2

Sample Input 2

3
2 3 1

Sample Output 2

1

Notes

Ví dụ 1: Tèo có thể chọn đoạn gồm các cây ~[2, 1, 2]~ để đốn và có thể bỏ qua cây ~[1]~ mà vẫn có thể đảm bảo số lượng bó củi tối thiểu theo yêu cầu của phú ông.

Ví dụ 2: Tèo chọn đốn đúng một cây ~[3]~ để đạt chỉ tiêu của phú ông.