P12360 [eJOI 2024] 足球决斗 / CF Duels

基希讷乌，摩尔多瓦的首都，有两支各由 $N$ 名球员组成的足球队，进行一系列的对决。为了增加趣味，他们按照以下一对一的方式安排比赛： - 总共有 $N$ 场对决，每场在不同的体育场进行。 - 每场对决将有两队中的一名球员对决。 - 每个球员将只参加一场对决。 - 每个体育场将为各自的对决胜利者提供一定金额的奖金。 - 技能等级更高的球员赢得对决。保证总有技能等级更高的球员。 在所有比赛结束后，冠军队是获得奖金总额超过对方球队的队伍。如果获得的奖金相同，则没有冠军。 你是第一支球队的经理，你的任务是安排你的 $N$ 名球员参加 $N$ 场对决获得冠军。 作为第一支足球队的经理，你拥有以下信息： - $N$ 个整数，表示你队伍中球员的技能等级 - $N$ 个整数，表示对方队伍中球员的技能等级 作为经理，你还派了一名侦查员访问每个体育场。侦查员按从 $1$ 到 $N$ 的顺序访问体育场，首先访问体育场 $1$，然后是体育场 $2$，最后访问体育场 $N$。侦查员访问完体育场 $i$ 后，他会向你报告对方球队在体育场 $i$ 的对决球员的技能等级。 可能在侦查员访问了一些体育场之后，你已经可以预见你的球队将成为冠军。换句话说，有可能在侦查员访问了一些体育场后，你可以确定你能成为冠军。**你可能仍然需要等待侦查员访问剩余的体育场，以便为你的球队建立分配方案。** 你的任务是找出侦查员需要访问的最少体育场数量，以确保你的球队能够夺冠，或者确定不可能成为冠军。

无

无

**【样例 #1 解释】** 对于第一个样例，在侦查员分享体育场 $1$ 和 $2$ 的信息后，你仍不能保证成为冠军。原因是，如果对手按以下方式安排球员： | 体育场 | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | | 奖金 | $1$ | $5$ | $4$ | $3$ | $1$ | | 对手球员技能等级 | $5$ | $9$ | $8$ | $12$ | $3$ | 你最好的选择是打成平局： | 体育场 | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | | 你的球员技能等级 | $6$ | $10$ | $1$ | $2$ | $4$ | 你将赢得体育场 $1,2,5$ 的比赛，获得奖金总额 $1+5+1=7$，而对手将赢得体育场 $3,4$ 的比赛，获得奖金总额 $4+3=7$。 在侦查员分享体育场 $1,2,3$ 的信息后，你可以确定你将成为冠军。原因是，如果对手按以下方式安排球员： | 体育场 | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | | 奖金 | $1$ | $5$ | $4$ | $3$ | $1$ | | 对手球员技能等级 | $5$ | $9$ | $3$ | 未知 | 未知 | 对手的两种选择是： | 体育场 | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | | 奖金 | $1$ | $5$ | $4$ | $3$ | $1$ | | 对手球员技能等级 | $5$ | $9$ | $3$ | $12$ | $8$ | | 你的球员技能等级 | $6$ | $10$ | $4$ | $1$ | $2$ | | 体育场 | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | | 奖金 | $1$ | $5$ | $4$ | $3$ | $1$ | | 对手球员技能等级 | $5$ | $9$ | $3$ | $8$ | $12$ | | 你的球员技能等级 | $6$ | $10$ | $4$ | $1$ | $2$ | 我们可以注意到，在这两种情况下，我们的球队将在体育场 $1,2,3$ 获胜，获得奖金总额 $1+5+4=10$，而对手将获得奖金总额 $3+1=4$。由于 $10>4$，我们可以确定在这两种情况下我们都会获胜，因此最小答案是 $3$。 **【样例 2 解释】** 对于第二个样例，可以证明，在侦查员提供体育场 $1,2$ 的信息后，你将首次确定成为冠军。然而，与第一个样例不同，你不会有一个固定的获胜分配。相反，对于对手在体育场 $3, 4, 5, 6$ 中的不同安排，你需要有不同的应对策略来赢得冠军。 **【数据范围】** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$12$|$p_i=1,N\le10$| |$2$|$16$|$p_i=1$| |$3$|$14$|答案为 $0$ 或 $1$| |$4$|$18$|答案为 $-1$ 或 $N-1$| |$5$|$10$|$n\le5$| |$6$|$30$|无| 对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^4,1 \le a_i,b_i \le 10^6$，且所有 $a_i,b_i$ 两两不同。