BCDは難易度順に逆転がないと進行できないのか

BCD コンテストには $N$ 問の問題が順番に並んでいる。現在 $j$ 番目にある問題の難易度は $A_j$ であり、すべての難易度は $1$ 以上 $M$ 以下の整数である。

実力が $s$ の参加者は、次の規則に従って問題を解く。

• 1 番目の問題から順番に確認する。
• 現在の問題の難易度が $s$ 以下なら、その問題を解いて次の問題に進む。難易度が参加者の実力と等しい場合も解くことができる。
• 難易度が $s$ を超える問題に初めて到達した時点で、ただちに終了する。その問題を飛ばしたり、それより後にある問題を解いたりすることはない。
• すべての問題を解いた場合は、そのまま終了する。

したがって、1 番目の問題から難しすぎる場合は 1 問も解くことができない。反対に、すべての問題の難易度が実力以下なら、$N$ 問すべてを解く。

各参加者について、次の 2 つの場合に解いた問題数を比較する。

1. 問題が 現在の順番に並んでいる状態で、上記の規則に従って問題を解く場合
2. 同じ問題を 難易度の昇順に並べ替えた後、最初から上記の規則に従って問題を解く場合

2 つの場合で解いた問題数が異なるなら、その参加者を ルナリティ式難易度配置の被害者と呼ぶ。同じ難易度の問題同士の順番は結果に影響しない。

例えば、難易度が $(2,1,5,4)$ で、参加者の実力が $4$ であるとする。現在の順番では、最初の 2 問を解いた後、難易度 $5$ の問題で止まる。それより後にある難易度 $4$ の問題は解かない。一方、昇順に並べた $(1,2,4,5)$ では 3 問を解く。したがって、実力が の参加者は被害者である。

実力が $1,2,\ldots,M$ の参加者がそれぞれ 1 人ずついる。このうち、ルナリティ式難易度配置の被害者の人数を求めよ。

入力は次の形式で与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、ルナリティ式難易度配置の被害者の人数を 1 行に出力せよ。

• $1\leq T\leq200\,000$。
• $1\leq N\leq200\,000$。
• $1\le M\le$。