Fat Sequence

Let the level $L_i$ of $A_i$ be the length of the longest increasing subsequence ending at $A_i$, and let $K = \max L_i$. All $L_i$ can be computed in $O(N \log N)$ with the well-known lower\_bound LIS algorithm.

Observation 1. In an increasing subsequence of length $K$, the $k$-th element has level exactly $k$. The first $k$ elements form an increasing subsequence, so the level is at least $k$. If it were larger than $k$, appending the remaining elements would give an increasing subsequence longer than , a contradiction.

Observation 2. Elements with the same level are non-increasing in index order. If $j < i$, $L_j = L_i$ and $$, then can be appended after , so , a contradiction.

Observation 3. Pick the largest value level by level from the top. Define $g_K, g_{K-1}, \cdots, g_1$ as follows.

• $g_K$ is the first element of level $K$, which is the one with the largest value.
• $g_k$ ($k$) is the first element of level whose value is smaller than . By Observation 2 it has the largest value among those elements.

Since $g_{k+1}$ has level $k+1$, some element of level $k$ lies before $g_{k+1}$ and has a smaller value. The element is the first such element, so its index is automatically before . Hence is an increasing subsequence of length .

Now take any increasing subsequence $h_1, h_2, \cdots, h_K$ of length . By Observation 1, has level . We show from downwards. The inequality follows from the definition of . If , then , and is the largest value of level below , so .

Therefore $h_k \leq g_k$ for every $k$, and $g$ is the fat sequence. Equal sums force all elements to be equal, so the values of the fat sequence are always unique.

Implementation. Bucket the elements by level while keeping index order. For each level, scan its list from the front until a value smaller than $g_{k+1}$ appears. Every list is scanned at most once, so this part is $O(N)$.

int bound = INT_MAX;
for (int k = K - 1; k >= 0; k--) {
    int p = st[k];
    while (a[ord[p]] >= bound) p++;
    pick[k] = a[ord[p]];
    bound = pick[k];
}

The total time complexity is $O(N \log N)$. The sum can reach about $10^{15}$, so a 64-bit integer is required.

The usual LIS reconstruction, which scans from the back and takes the first matching element, picks the smallest possible value on every level and is wrong. Also note that the increase is strict. Using upper\_bound instead of lower\_bound fails on inputs with equal values.

Solutions for the subtasks.

• Subtask 1: check every subsequence in $O(2^N N)$.
• Subtask 2: an $O(N^2)$ DP whose state is the lexicographically largest pair $(\text{length}, \text{sum})$, followed by backtracking.

Solution written by ClaudeOpus5.5