「Wdoi-3」夜雀 singing

“唉，今天可真是多事的一天呢。不过一晚的忙碌结束了，接下来就是我尽展歌喉的时刻啦！” 作为幻想乡妖精中的一份子，米斯蒂娅在闲暇之余（也就是夜雀食堂闭店之后）也会去参加由夜雀们自发组织而成的夜雀歌会。夜雀们会按照一种约定好的方式进行歌唱。在今夜的歌会中，米斯蒂娅成为了歌会的组织者。 然而因为大家都是夜雀，因此所谓的“舞台”其实是由若干个高度不一的树组成的。夜雀都会飞（显然），因此它们可以不断地变换自己的位置。 然而，由于夜雀的数目实在是太多，以至于作为组织者的米斯蒂娅搞不清楚活动的组织方案了。你能帮帮她吗？

我们可以将这 $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$ 的树上。 但这样一些夜雀可能无法顺利完成歌会，会遇到“无处可走”的情况，于是夜雀们决定选择若干个大树作为飞行点。如果一个夜雀到达了某个飞行点，那么下一时刻她除了能移动到编号相邻的树上，还能**到达其他的飞行点**。 然而，飞行点太多容易使得歌会变得非常混乱。因此，米斯蒂娅希望最小化飞行点的数目。你能帮帮她吗？

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

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

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

#### 样例 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$ 的合法解。因此本题不会存在无解情况。