测试若歪

Problem Description

在 ICPC 赛制的比赛中，选手经常利用排行榜来估计题目难度，进而决定自己的做题顺序。然而排行榜具有偶然性，很多时候不能真实反映真正的难度顺序，这种情况被称为歪榜。 现有一场比赛共有 $n$ 道题，比赛时按时间顺序产生了 $m$ 条通过记录，其中的第 $i$ 条通过记录通过了第 $p_i$ 题。 我们定义：

• 这场比赛的实际难度顺序是把所有题按照被通过次数从高到低排序后的结果。通过次数相同的题，题号小的排在前面。
• 这场比赛的赛时做题顺序是把所有题按照首次被通过的时间从早到晚排序的结果。没有通过的题排在末尾，且这些题之间，题号小的排在前面。 你为了测试比赛是否发生了歪榜，想要比较实际难度顺序和赛时做题顺序之间有几个位置不同。

Input

本题有多组测试数据。 输入的第一行有一个正整数 $T$（$1\le T\le 10^5$），表示测试数据的组数。 对于每组测试数据输入两行： 第一行是两个正整数 $n,m$（$1\le n,m\le 10^5$），分别表示题目数和提交记录数。 第二行有 $m$ 个正整数 $p_1,\ldots,p_m$，表示提交记录。 保证所有测试点的 $m$ 之和不超过 $10^6$。注意：所有测试点的 $n$ 之和没有保证。

Output

对于每组测试数据，输出一行一个正整数，表示答案。

Sample Input

1
4 5
1 3 3 1 3

Sample Output

2

Hint

【样例解释】 比赛共有 $4$ 道题，有 $5$ 个通过记录。 实际难度顺序是 $3,1,2,4$，而赛时做题顺序是 $1,3,2,4$，有 $2$ 个位置（第 $1,2$ 个位置）不同。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）