Description

我们可以将这 $n$ 棵树从 $1$ 到 $n$ 编号。其中，在 $m$ 个点上分布着参加舞会的夜雀。第 $i$ 棵树的高度为 $h_i$ 。

夜雀们的歌会一共会进行 $t$ 时刻。第 $i$ 个时刻，夜雀们只能在高度严格大于 $i$ 的树上唱歌。因为这些树木都是事先被选择好的，因此总是有 $\max\{h_i\}>t$。夜雀们每个时刻，可以选择站着不动，或移动到编号相邻的一棵树上（例如，原先在编号为 $i$ 的树上的夜雀，下个时刻可以移动到编号为 $i-1$ 或者 $i+1$ 的树上。不过，她们不能移动到编号为 $0$ 或 $n+1$ 的树上）。初始时为第 $0$ 时刻。也就是说，假使一个夜雀初始时在高度为 $1$ 的树上，那么她下一时刻不得不去高度大于 $1$ 的树上。

但这样一些夜雀可能无法顺利完成歌会，会遇到“无处可走”的情况，于是夜雀们决定选择若干个大树作为飞行点。如果一个夜雀到达了某个飞行点，那么下一时刻她除了能移动到编号相邻的树上，还能到达其他的飞行点。

然而，飞行点太多容易使得歌会变得非常混乱。因此，米斯蒂娅希望最小化飞行点的数目。你能帮帮她吗？

Input Format

第一行三个整数 $n,m,t$。含义如题面所示。
第二行 $n$ 个整数，第 $i$ 个整数表示 $h_i$。
第三行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 只夜雀的位置 $p_i$。

Output Format

输出一行，一个整数，表示最少的飞行点数量。

5 3 4
1 2 1 4 5
5 3 2 

2

10 7 9
8 1 1 5 13 10 1 1 6 3 
2 4 7 10 6 8 9 

3

Hint

样例 1 解释

一个最优方案是，分别在第 $2,5$ 棵树建立飞行点，下表为各夜雀的一个可行移动方案：

$$\def\arraystretch{1.8} \begin{array}{|c|c|c|c|} \hline \textsf{\textbf{夜雀编号}} & \textsf{\textbf{时刻 $0$ 所在位置}} & \textsf{\textbf{时刻 $1$ 所在位置}} & \textsf{\textbf{时刻 $2 \sim 4$ 所在位置}} \cr\hline \textsf1 & 5 & 5 & 5 \cr\hline \textsf2 & 3 & 2 & 5 \cr\hline \textsf3 & 2 & 5 & 5 \cr\hline \end{array}$$

可以证明不存在更优解。

---

数据范围及约定

$$\def\arraystretch{1.6} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \cr\hline 1 & 16 & - & 15 \cr\hline 2 & 5\times 10^5 & \text{A} & 5 \cr\hline 3 & 5\times 10^5 & \text{B} & 15 \cr\hline 4 & 10^3 & - & 25 \cr\hline 5 & 5\times 10^5 & - & 20 \cr\hline 6 & 5\times 10^6 & - & 20 \cr\hline \end{array}$$

• 特殊性质 A：$\min(h_i) > t$。
• 特殊性质 B：$t > n$ 且 $h_i \in \{1,t-1,t+1\}$。

对于 $100\%$ 的数据，满足 $1 \le n,m \le 5 \times 10^6$，$1 \le h_i,t \le 10^9$，$1 \le p_i \le n$。保证 $p$ 互不相同，且 $\max(h_i) > t$。

---

提示

显然你可以将所有位置都作为飞行点，然后在第 1 时刻让所有夜雀都飞到一棵 $h_i > t$ 的树来得到一组答案为 $n$ 的合法解。因此本题不会存在无解情况。