便利のため，\(A_0=0,A_{N+1}=N+1\) と定義し，\(A_0,A_{N+1}\) を含む部分列を数えることにします．

今，\(0 = x_0 <x_1< \cdots < x_k < x_{k+1}=N+1\) に対し，部分列 \(s=(A_{x_0},A_{x_1},\cdots,A_{x_{k+1}})\) を取り出す方法が一意であったとします．

このとき，各 \(0 \leq i \leq k\) について，次のことが成立する必要があります．

• \(A_{x_i+1},A_{x_i+2},\cdots,A_{x_{i+1}-1}\) の中に，\(A_{x_i}\) または \(A_{x_{i+1}}\) と同じ値が存在しない．

この条件を満たさないと，同じ部分列を取り出す方法が別に存在することになります．

逆に，上記の条件を満たす場合，\(s\) を取り出す方法は一意です． これは，\(A\) の先頭から \(s\) を貪欲に取り出す方法（つまり，使う添字を辞書順最小にする方法）と，\(A\) の後ろから \(s\) を貪欲に取り出す方法（つまり，添字を辞書順最大にする方法）が一致することから示せます．

よって，この条件を満たす添字列 \(x\) を数えればよいです． これは，Binary Indexed Tree を使って実装することができます． 計算量は \(O(N \log N)\) になります．