Maximum Diameter of a Weighted Tree

Paimon has found a tree with \(n+1\) vertices (all initially white) and an integer sequence \(a_1, a_2, \cdots, a_n\). A tree with \(n+1\) nodes has exactly \(n\) edges and is a connected undirected graph.

The tree is constructed in the following manner:

1. Select any vertex in the tree and paint it black.
2. For \(i = 1\) to \(n\), perform the following operation:
   1. Select a white vertex \(x_i\) that is directly connected to some black vertex \(y_i\) by an edge.
   2. Assign the weight \(a_i\) to the edge \((x_i, y_i)\) and paint \(x_i\) black.

After these operations, you obtain a weighted tree where each edge has a weight from the given sequence. You have the freedom to choose the initial vertex and, at every step, which white vertex to paint so that the final tree structure can be arbitrarily designed under these rules.

Your task is to maximize the diameter of the weighted tree. The diameter of a weighted tree is defined as the maximum length among all simple paths, where the length of a path is the sum of the weights of the edges on that path.

Observation:

• You can build a chain (a simple path without branches) consisting solely of edges with positive weights. In this case, the diameter will be the sum of those positive weights.
• If all \(a_i\) are non-positive (i.e. negative or zero), then you can arrange the tree as a star so that the maximum simple path is just one edge with the maximum weight among \(a_1, a_2, \ldots, a_n\).

Thus, the answer is computed as follows:

[ \text{diameter} = \begin{cases} \sum_{i ; \text{such that} ; a_i>0} a_i, & \text{if there exists at least one } a_i > 0,\ \max_{1 \le i \le n} a_i, & \text{if } a_i \le 0 \text{ for all } i. \end{cases} ]

Given the sequence \(a_1, a_2, \ldots, a_n\), compute the maximum possible diameter of the weighted tree you can construct.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), denoting the number of operations (and the number of edges in the tree).

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)), representing the weights assigned in each operation.

outputFormat

Output a single integer — the maximum possible diameter of the weighted tree.

sample

3
1 -2 3

4