Overview

This problem asks us to divide a sequence of cards into several non-increasing piles.
We want to minimize the number of piles, and subject to that, maximize the sum \(B_1+B_2+\cdots+B_N\).

Analysis

If we process the cards from left to right, we can minimize the number of piles using a typical greedy strategy of choosing which pile to place each card on. However, this does not guarantee that the sum of \(B_i\) is maximized.

Therefore, let’s consider processing from right to left.

In the original rules, the condition under which card \(j\) can be placed on top of card \(i\) is:

\[ i < j,\quad A_i \geq A_j \]

If we view this from right to left, let \(x\) be the value of the “current bottommost card” of an already created pile, and \(y\) be the value of the card we want to add below it. The condition becomes:

\[ x \leq y \]

If this holds, we can add the card below that pile.

In other words, processing from right to left reduces the problem to:

• If the bottommost value of an existing pile is less than or equal to \(A_i\), we can place card \(i\) below it.
• If there is no such pile, we must create a new pile.

If there are multiple piles where we can place the card, we choose the pile with the maximum bottommost value among those less than or equal to \(A_i\).

This is a typical greedy choice. By using a pile with a larger value, we preserve piles with smaller values. This is because piles with smaller values are more likely to be able to accept cards further to the left in the future.

For example, suppose the current bottommost values of the piles are:

\[ 1,\ 5 \]

and the value of the card we are currently looking at is \(6\).

• If we place it on the pile with value \(1\), the remaining bottommost values will be \(5,\ 6\).
• If we place it on the pile with value \(5\), the remaining bottommost values will be \(1,\ 6\).

The latter is more advantageous for the future because we keep the pile with value \(1\).

---

Next, let’s consider why this also maximizes the sum of \(B_i\).

In a certain pile, suppose the cards are stacked from bottom to top in the order:

\[ c_1, c_2, \ldots, c_m \]

In this case,

\[ B_{c_1}=0,\quad B_{c_2}=c_1,\quad B_{c_3}=c_2,\quad \ldots \]

That is, the index of “each card that has another card on top of it” is added exactly once to the sum of \(B\).
In other words,

\[ B_1+B_2+\cdots+B_N = 1+2+\cdots+N - \text{sum of the indices of the topmost cards of each pile} \]

If the number of piles \(K\) is fixed, maximizing the sum of \(B\) is equivalent to minimizing the sum of the indices of the topmost cards of each pile.

When processing from right to left, the card at the moment a new pile is created becomes the “topmost card” of that pile.

Therefore, using the right-to-left greedy strategy:

• Place the card below an existing pile if possible.
• Create a new pile only when it cannot be placed.

This allows us to create new piles as far to the left (i.e., with indices as small) as possible.

As a result, the sum of the indices of the topmost cards of each pile is minimized, and \(B_1+B_2+\cdots+B_N\) is maximized.

Algorithm

We process the cards from right to left.

For each pile, we maintain its current “bottommost card”.
When processing card \(i\), let its value be \(A_i\).

Operations

1. Find the existing piles whose bottommost card’s value is less than or equal to \(A_i\).
2. Among them, choose the pile with the maximum bottommost value.
3. If such a pile exists:
   • Let \(j\) be the current bottommost card of that pile.
   • Place card \(i\) directly below card \(j\).
   • Thus, \(B_j=i\).
   • Update the bottommost card of the pile to \(i\).
4. If no such pile exists:
   • Create a new pile.
   • Increase the number of piles \(K\) by \(1\).

Data Structure

Since \(A_i\) can be up to \(10^9\), we use coordinate compression.

With that, we maintain the following:

• stacks[r]
  • A list of the “current bottommost card indices” whose compressed rank of value is \(r\).
• Fenwick Tree
  • For each rank \(r\), maintain how many piles currently have this value at the bottom.

Let \(r\) be the compressed value of card \(i\).

Using the Fenwick Tree, we find:

\[ \text{the number of piles with ranks from } 1 \text{ to } r \]

If this is \(0\), there are no piles where we can place the card.

If it is not \(0\), we binary search on the Fenwick Tree to find the maximum rank \(p\) (\(p \le r\)) that exists.
We take one pile of rank \(p\) and place card \(i\) below it.

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

Coordinate compression takes \(O(N \log N)\) time, and processing each card takes \(O(\log N)\) time due to Fenwick Tree operations.

Implementation Points

In the Fenwick Tree, we maintain the count of the current “bottom of the pile” for each value.

s = prefix_sum(r)

Using this, we check if there exists a pile with a value less than or equal to \(A_i\).

If it exists, s is the “number of piles with rank less than or equal to \(r\)”.
By searching for the “minimum position where the prefix sum is at least s” on the Fenwick Tree, we can find the maximum existing rank that is less than or equal to \(r\).

Also, when placing card \(i\) below an existing pile, let \(j\) be the card that was originally at the bottom of that pile. We set:

b[j] = i

This means “card \(i\) is directly below card \(j\)”.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]

    vals = sorted(set(a))
    comp = {v: i + 1 for i, v in enumerate(vals)}
    ranks = [comp[x] for x in a]
    m = len(vals)

    bit = [0] * (m + 1)
    stacks = [[] for _ in range(m + 1)]
    b = [0] * (n + 1)

    def add(i, v):
        while i <= m:
            bit[i] += v
            i += i & -i

    top_bit = 1 << (m.bit_length() - 1)

    k = 0

    for pos in range(n - 1, -1, -1):
        idx_card = pos + 1
        r = ranks[pos]

        s = 0
        x = r
        while x > 0:
            s += bit[x]
            x -= x & -x

        if s == 0:
            k += 1
            stacks[r].append(idx_card)
            add(r, 1)
        else:
            idx = 0
            need = s
            step = top_bit
            while step:
                nxt = idx + step
                if nxt <= m and bit[nxt] < need:
                    idx = nxt
                    need -= bit[nxt]
                step >>= 1

            p = idx + 1
            below = stacks[p].pop()
            b[below] = idx_card
            stacks[r].append(idx_card)

            if p != r:
                add(p, -1)
                add(r, 1)

    sys.stdout.write(str(k) + "\n" + " ".join(map(str, b[1:])) + "\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.