まず、 \(s=B_1+B_2+\dots+B_N\) について検討します。
カード \(i\) の直下にカードが無い時 \(B_i=0\) 、直下にカード \(j\) がある時 \(B_i=j\) です。これを逆の視点から捉えます。
「カード \(j\) の上に何らかのカードが乗せられたとき \(s\) に \(j\) 加算する」と捉えても \(s\) の値は計算できます。

更に、本問題自体も時系列を逆向きに捉えます (俗に 逆から見る などと言われる発想です)。

• \(i=N,N-1,\dots,1\) の順に、以下のいずれかを実行することを繰り返す。
  • 新しい山を作る。 \(s\) に \(0\) 加算する。
  • 一番下のカードを \(y\) としたとき、 \(y \le A_i\) を満たす山をひとつ選ぶ。この時、その山の一番下にカード \(i\) を追加し、 \(s\) に \(i\) 加算する。

こうすると、 \(s\) の最大化について多少考えやすくなります。

このもとで、実は以下の貪欲法が最適解の \(1\) つを与えます。

• 山の集合を \(S\) とする。最初 \(S\) は空である。
• \(i=N,N-1,\dots,1\) の順に、以下を繰り返す。
  • 各山の一番下のカードを \(y\) としたとき、もし \(S\) の中に \(y \le A_i\) なるものが存在すれば、そのうち \(y\) が最大となるものを \(1\) つ選び、その山の一番下にカード \(i\) を追加する。
  • そうでないといき、カード \(i\) を単独で新たな \(1\) 個の山とする。

この貪欲法の正当性の説明を、具体例をもって示します。
現在、各山の一番下が \((10,30,50)\) であるとします。
まず、ここに \(5\) が追加される場合を考えます。この場合、この状況からは山を増やすしかありません。
次に、ここにカード \(j\) として \(35\) が追加される場合を考えます。
この時、考えうる行動としては以下の \(3\) 通りです。

1. \(10\) の下に追加する。
2. \(30\) の下に追加する。
3. \(35\) を単独で新たな \(1\) つの山とする。

各山の一番下がどう変化するか考えます。

1. \((30,35,50)\) となる。
2. \((10,35,50)\) となる。
3. \((10,30,35,50)\) となる。

より大きなカードを下に敷くという面で、 1. は 2. の下位互換になっているため、 1. を選択する意味はありません。
また、 2. と 3. とを比較した時、 2. では \(j\) 点を得ている代わりに 3. では山がひとつ増えています。
3. の行動を行った後、更に進めた状況を考えます。
もし \(10,35,50\) が一番下となっている山の下に追加した時は、 2. でも同じ行動ができます。もし \(30\) が一番下となっている山の下に追加した時は、 2. で新たな山を作ることができます。このとき失う得点は \(j\) 点未満です。また、最後まで \(30\) の下に追加しない場合は単に \(j\) 点を損することになります。
以上より、 3. も 2. の下位互換であることがわかりました。

以上より、この貪欲法の最適性が分かります。

本解法の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N;
  cin >> N;
  vector<ll> A(N+1);
  for(ll i=1;i<=N;i++){cin >> A[i];}

  vector<ll> B(N+1,0);
  set<pl> ms;
  for(ll i=N;i>=1;i--){
    auto it=ms.lower_bound({A[i]+1,-1});
    if(it!=ms.begin()){
      it--;
      B[(*it).second]=i;
      ms.erase(it);
    }
    ms.insert({A[i],i});
  }
  cout << ms.size() << "\n";
  for(ll i=1;i<=N;i++){
    if(i-1){cout << " ";}
    cout << B[i];
  }cout << "\n";
  return 0;
}