An có một thanh Sô cô la và muốn chia cho các bạn. Thanh sô cô la được mô tả như một bảng có kích thước ~2 \times N~, mỗi phần thanh sô cô la là một ô trong bảng có giá trị ~T_{i,j}~ (~0 \le T_{i,j} \le 10^8~) thể hiện độ ngon của từng phần. An muốn chia toàn bộ thanh sô cô la thành các phần liên thông với nhau sao cho độ ngon trung bình của mỗi phần là như nhau. Mỗi phần được xem là liên thông nhau nếu mỗi ô trong các phần chung cạnh.

Yêu cầu: Hãy giúp An chia thanh sô cô la thành nhiều phần liên thông nhất mà độ ngon trung bình của mỗi phần là bằng nhau.

Input

• Dòng 1 chứa số nguyên dương ~N~ (~1 \le N \le 200000~) là độ dài thanh sô cô la.
• Dòng thứ 2 chứa ~N~ số nguyên biểu thị dòng đầu của thanh sô cô la, số thứ ~j~ biểu diễn ~T_{1,j}~.
• Dòng thứ 3 chứa ~N~ số nguyên biểu thị dòng cuối thanh sô cô la, số thứ ~j~ biểu diễn ~T_{2,j}~.

Output

• Một số nguyên duy nhất là số thành phần liên thông nhiều nhất mà An chia được.