👑PhuocThien (Div. 02) - Mừng Ngày Quốc Tế Thiếu Nhi

Hôm nay PhuocThien làm thầy giáo của \(1\) đội múa trong đó có \(N\) bạn muốn được tuyển vào. Bạn thứ \(i\) có chiều cao là \(a_i\). Vì là \(1\) người lười biếng nên PhuocThien đã nghĩ ra cách chọn \(1\) đội là cho các bạn có chiều cao liên tiêp không giảm nhiều nhất.

Yêu cầu

Hãy tìm ra số lượng thành viên trong đội múa được chọn.

Input

• Dòng \(1\): Gồm \(1\) số nguyên dương \(N\). \((1 \le N \le 10^6)\).
• Dòng \(2\): Gồm \(N\) số nguyên dương \(a_1, a_2, a_3, ..., a_N\). \((1 \le a_i \le 1000)\)

Output

• \(1\) dòng gồm kết quả bài toán.

Example

8
1 2 3 4 5 2 1 2

5

Gọi 𝕌𝕏\((n)\) là tổng ước của \(n\) nhân với số lượng ước của \(n.\)
Cho số nguyên dương \(N\) số đó được gọi là số đẹp nếu nó thỏa mản điều kiện \(:\)

• 𝕌𝕏\((n + 1)\) \(<\) 𝕌𝕏\((n)\) \(>\) 𝕌𝕏\((n - 1).\)

Yêu cầu

kiểm tra số \(N\) có phải là số đẹp hay không.

Input

• Cho \(Q\) truy vấn \((1 \le Q \le 1000).\)
• Với mỗi truy vấn nhập số nguyên dương \(N\) \((1 \le N \le 10^6).\)

Output

• với mỗi truy vấn nếu \(N\) là số đẹp in ra Yes , ngược lại thì in ra No \(.\)

Example

5
1 2 6 12 24

No
No
Yes
Yes
Yes

Có \(N\) cây táo được xếp thành một hàng, cây thứ \(i\) cho \(a_i\) quả táo. Bạn muốn chọn một số cây để hái táo sao cho không có hai cây nào được chọn đứng cạnh nhau. Hãy tìm số táo lớn nhất có thể hái được.

Input

• Dòng đầu tiên chứa một số nguyên \(N\). \((1 \le N \le 2 \cdot 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9 \le a_i \le 10^9)\)

Output

• In ra một số nguyên duy nhất là số táo lớn nhất có thể hái được.

Example

5
3 2 7 10 1

13

Sau một sự cố an ninh mạng toàn cầu, mạng lưới máy chủ lõi gồm \(N\) máy chủ được kết nối với nhau dưới dạng một cấu trúc cây gồm \(N-1\) cáp nối quang. Mỗi cáp nối giữa máy chủ \(u\) và \(v\) có một băng thông truyền tải là \(w\). Để tái cấu trúc hệ thống một cách an toàn, bạn cần chọn ra đúng \(k\) cáp nối sao cho không có máy chủ nào kết nối trực tiếp với quá \(2\) cáp nối được chọn (tức là các cáp nối được chọn phải tạo thành một tập hợp các đường đi rời nhau về mặt đỉnh trên cây). Hãy xác định tổng băng thông lớn nhất có thể đạt được với mọi cấu hình chọn từ \(1\) đến \(N-1\) cáp nối.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 300\)) — số lượng máy chủ.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) (\(1 \le u, v \le N, |w| \le 10^9\)) mô tả một cáp nối giữa hai máy chủ \(u\) và \(v\) với băng thông \(w\).

Output

• In ra \(N-1\) số nguyên trên một dòng, số thứ \(k\) thể hiện tổng băng thông lớn nhất có thể đạt được khi chọn đúng \(k\) cáp nối thỏa mãn điều kiện. Nếu không thể chọn được đúng \(k\) cáp nối, in ra -1.

Example

5
1 2 5
2 3 10
3 4 -2
3 5 7

10 17 22 -1