Sau khi leo rank Thách đấu thành công trong LTOJ, TuanAnh đã quyết định dành một đêm Giáng Sinh thật đặc biệt. Anh rủ AKA và trưởng thôn Minh đi dạo phố để tận hưởng không khí Noel.
AKA là một người rất yêu thích mọi thứ đối xứng, giống như cái tên của anh ấy. Trưởng thôn Minh cũng rất thích đối xứng, bởi vì Minh thích mọi điều bắt đầu bằng chữ M, chẳng hạn như Man Utd, Mordekaiser, Manbo, và đặc biệt chữ cái M cũng mang tính đối xứng. Để tặng món quà trước khi qua Úc, TuanAnh quyết định tạo ra một món quà đặc biệt mang tính đối xứng từ những quả cầu tuyết trên phố.
Dọc theo con đường, có rất nhiều quả cầu tuyết với kích thước ai TuanAnh muốn gom chúng lại để tạo thành một dãy đối xứng hoàn hảo. Trong một lần gộp, TuanAnh có thể chọn hai quả cầu tuyết liền kề và gộp chúng lại thành một quả cầu mới, với kích thước bằng tổng kích thước của hai quả cầu ban đầu.
Vì số quả cầu quá nhiều, hãy giúp TuanAnh tính số lần gộp tối thiểu cần thiết để biến dãy ban đầu thành một dãy đối xứng.

Input

• Dòng \(1\): Chứa \(1\) số nguyên dương \(N\) \((1 \leq N \leq 10^5)\) là số lượng quả cầu tuyết.
• Dòng thứ hai chứa N số nguyên \(a_i (1≤ a_i ≤ 10^6)\) , là kích thước của các quả cầu tuyết

Output

• In ra một số nguyên duy nhất là số lần gộp tối thiểu cần thực hiện để biến dãy cầu tuyết thành một dãy đối xứng.

Example

5
3 10 6 4 3

1

ABNL có thể gộp quả cầu tuyết có kích thước 6 và 4 lại với nhau, tạo thành dãy đối xứng  [3,10,10,3] với chỉ 1 lần gộp.

3
2 1 4

2

ABNL cần gộp 2 và 1 lại với nhau, sau đó gộp phần này với 4, tạo thành dãy đối xứng [7]. Tổng cộng cần 2 lần gộp.

Sau đêm chung kết đau họng ASEAN Mitsubishi Electric Cup 2024, vì vẫn còn vui, 2 lớp A,B khối 9 thách thức nhau trên sân cỏ.

nhatminhlt_2010 được phân làm người ghi lại lớp, tên và phút mỗi khi có người ghi bàn, nhatnamlt thì phân tích trận đấu sau tiếng còi kết thúc.

Cả 2 lớp muốn nhatnamlt liệt kê thông tin trên các dòng như sau:

• Dòng 1: In ra 2 số \(P\), \(Q\) lần lượt là số lượng bàn thắng của đội A và đội B. 2 số cách nhau bằng dấu ' \(:\) '
• Dòng 2: In "A:"
• \(L\) dòng tiếp theo: In ra tên, thời gian ghi bàn của mỗi người ở đội A (nếu họ ghi bàn) trên nhiều dòng, mỗi thông tin cách nhau 1 dấu cách. Nếu một người ghi được nhiều bàn, in thời gian ghi bàn của họ lần lượt theo vị trí tương đối ở trong vở, cách nhau bằng dấu ' \(,\) '. Thứ tự in ra sắp xếp tăng dần tên theo thứ tự từ điển. Nếu không có bàn thắng, in ra \(0\)
• Dòng \(L\)+1: In ra "B:"
• \(K\) dòng tiếp theo: In ra tên, thời gian ghi bàn của mỗi người ở đội B (nếu họ ghi bàn) trên nhiều dòng, mỗi thông tin cách nhau 1 dấu cách. Nếu một người ghi được nhiều bàn, in thời gian ghi bàn của họ lần lượt theo vị trí tương đối ở trong vở, cách nhau bằng dấu ' \(,\) '. Thứ tự in ra sắp xếp tăng dần tên theo thứ tự từ điển. Nếu không có bàn thắng, in ra \(0\)

Yêu cầu:

Giúp nhatnamlt hoàn thành danh sách.

Dữ liệu vào:

• Dòng 1: Nhập vào \(N\) (\(N<=90\)) là số lượng bàn được ghi trong trận.
• \(N\) dòng tiếp theo: Lần lượt là tên lớp, tên và thời gian (\(t<=N\)) ghi bàn, mỗi thông tin cách nhau 1 dấu cách.

9
A Vinh 8
A Anh 15
B Cuong 31
A Vinh 44
B Nhan 56
B Quang 81
A Hoang 84
B Cuong 87
A Hoai 90

5:4
A:
Anh 15
Hoai 90
Hoang 84
Vinh 8,44
B:
Cuong 31,87
Nhan 56
Quang 81

Xét một thuật toán với đầu vào là một số nguyên dương \(n\). Nếu \(n\) là số chẵn, thuật toán chia \(n\) cho hai; nếu \(n\) là số lẻ, thuật toán nhân \(n\) với ba và cộng thêm một. Thuật toán lặp lại quá trình này cho đến khi \(n\) trở thành một.

Ví dụ, với \(n = 3\), dãy số là:

\(3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)

Nhiệm vụ của bạn là mô phỏng quá trình thực hiện thuật toán này với một giá trị \(n\) cho trước.

Input

Dòng duy nhất chứa một số nguyên \(n (1 \leq n \leq 10^6)\)

Output

In ra một dòng chứa tất cả các giá trị của \(n\) trong quá trình thực hiện thuật toán.

Ví dụ

Dữ liệu vào:

3

Kết quả ra:

3 10 5 16 8 4 2 1