fork()==0世界线变动

给出一个长度为n的浮点数数组a。数组每个值在0到1之间。

现在你要n个人出题。

第i个人出题成功的概率为a[i]

如果可以从n个人中选一些人出题，恰好只有一个人出题的最大概率是多少？

给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。

你可以对排列 $p$ 进行下列操作任意次：

• 选择整数 $i,j(1\leq i<j\leq n)$，然后交换 $p_i,p_j$ 的值。

你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。

每个测试点包含 $t$ 组数据。

输入格式

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据：

第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。

接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p$ 是一个 $1\sim n$ 的排列。

输出格式

对于每组数据：

输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。

可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

小 P 有 $n$ 场考试要考，它们的开始时间是 $a_1\sim a_n$（保证 $a$ 按升序排列），所有的考试都会在 $d$ 之前结束。

对于时间相邻的两场考试 $a_{i-1},a_{i}$，定义它们的距离为 $a_{i}-a_{i-1}-1$，而 $a_1$ 与 $a_{0}$ 的距离定义为 $a_1$ 与 $0$ 的距离。

定义对于这个数组 $a$ 的 $\mu$ 值为所有 $a_{i-1}$ 与 $a_{i}$ 之间距离的最小值。

你可以改变某一个 $a_i$ 的值（但不能 $>d$），最大化修改后 $a$ 的 $\mu$ 的值，输出最大的 $\mu$ 值。

翻译提供者：@DaiRuiChen007

在$n\times n$的网格上，有若干目标。从最低下扔回旋镖，碰到目标会右转。每行、每列不超过两个目标。现在已知从每一列扔出去会撞到$a_i$个障碍($a_i\le 3$)，请求出一种合法方案。

翻译 by jun头吉吉

有一天，_rqy想出来了一道构造题，出给了wqy去做。然而wqy不会做，于是就来找你。

你有一个$n$行$m$列的棋盘，其中第$i$行第$j$列的格子标号为$(i,j)$。你需要从$(1,1)$开始遍历这个棋盘。每一次，如果你在$(x,y)$，你可以选择一个向量$(\text{d}x,\text{d}y)$，并且移动到$(x+\text{d}x,y+\text{d}y)$这个格子上。

你不能离开这个棋盘，同时每一个向量只能使用一次。你的任务是合理安排自己的行走路线，使得每一个格子都只被经过一次。输出这个方案。

wqy翻译了那么多题面，你一定要帮他解出来！

给定数据组数 $t$，每组数据包含正整数 $n$、$k$，求满足 $x\geq n$ 的最小正整数 $x$，使 $x$ 是个 $k$-beautiful 数。

一个正整数是个 $k$-beautiful 数，当且仅当其无前导零的十进制数值表示中，不同的数字不超过 $k$ 个。

数据满足 $1 \leq t \leq 10^4$，$1 \leq n \leq 10^9$，$1 \leq k \leq 2$。

有 $n$ 个战士站成一排，第 $i$ 个战士的战力是 $a_i$。所有战士的战力都是两两不同的。

你可以使用两种类型的咒语：

1. 火球术：你可以消耗 $x$ 点法力值来干掉连续的 $k$ 个战士（你必须干掉正好 $k$ 个，而不能干掉 $\le k$ 个）。

2. 狂暴术：你可以消耗 $y$ 点法力值，选择站在一起的两个战士使他们展开决斗，战力较弱的那个战士将会被干掉。

我们来举个例子，假设有 $7$ 个战士，其战力分别为 $[2,3,7,8,11,5,4]$，且此时的$k=3$（$k$ 的定义详见火球术）。如果你对战力为 $8$ 与 $11$ 的两个战士施加狂暴术，剩下战士的战力将会变成 $[2,3,7,11,5,4]$（战力为 $8$ 的战士在决斗中战死）。然后如果我们对战力为 $[7,11,5]$ 的战士施加火球术，剩下战士的战力将会变成 $[2,3,4]$。

你想要组建一支军队，因此你想要将所有战士战力的序列从 $a_1,a_2,\cdots,a_n$ 变为 $b_1,b_2,\cdots,b_m$。试计算你所需的最少法力值。

输入格式

第一行两个整数 $n,m (1\le n,m\le 2\cdot 10^5)$ ——序列 $a$ 的长度和序列 $b$ 的长度。

第二行三个整数 $x,k,y (1\le x,y\le 10^9,1\le k\le n)$ ——火球术消耗的法力值，火球术的范围和狂暴术消耗的法力值。

第三行 $n$ 个整数 $a_1,a_2,…,a_n (1\le a_i\le n)$。保证 $a_i$ 是两两不同的。

第四行 $m$ 个整数 $b_1,b_2,…,b_m(1\le b_i\le n)$。保证 $b_i$ 是两两不同的。

输出格式

一行一个整数，即将序列从 $a_1,a_2,\cdots,a_n$ 变为 $b_1,b_2,\cdots,b_m$所需的最少法力值。如果无法完成变换，则输出$-1$。