Background

“Sigh, today has really been a troublesome day. But after a whole night of work is over, it’s finally time for me to show off my singing!”

As one of the fairies in Gensokyo, Mystia, when she has free time (that is, after the Night Sparrow Diner closes), also goes to a night sparrow singing party that is organized spontaneously by the night sparrows. The night sparrows sing in an agreed-upon way. At tonight’s party, Mystia becomes the organizer.

However, since everyone is a night sparrow, the so-called “stage” is actually made up of several trees of different heights. Night sparrows can fly (obviously), so they can keep changing their positions.

But because the number of night sparrows is simply too large, Mystia, as the organizer, cannot figure out the plan for organizing the event. Can you help her?

Problem Description

We number these $n$ trees from $1$ to $n$. There are $m$ night sparrows participating in the party distributed on $m$ positions. The height of the $i$-th tree is $h_i$.

The singing party lasts for a total of $t$ time moments. At moment $i$, the night sparrows can only sing on trees whose height is strictly greater than $i$. Since these trees are chosen in advance, we always have $\max\{h_i\}>t$. At each moment, a night sparrow may choose to stay still, or move to a tree with an adjacent index (for example, a night sparrow originally on the tree with index $i$ may move to index $i-1$ or $i+1$ at the next moment. However, they cannot move to the trees with index $0$ or $n+1$). The initial state is at moment $0$. That is, if a night sparrow initially is on a tree of height $1$, then at the next moment she must go to a tree with height greater than $1$.

But in this way, some night sparrows may not be able to finish the party smoothly, and may encounter a situation of “nowhere to go”. So the night sparrows decide to choose some tall trees as flight points. If a night sparrow reaches a flight point, then at the next moment, besides moving to adjacent-index trees, she can also reach other flight points.

However, having too many flight points makes the party very chaotic. Therefore, Mystia wants to minimize the number of flight points. Can you help her?

Input Format

The first line contains three integers $n,m,t$, with meanings as described above.
The second line contains $n$ integers, where the $i$-th integer denotes $h_i$.
The third line contains $m$ integers, where the $i$-th integer denotes the position $p_i$ of the $i$-th night sparrow.

Output Format

Output one line with one integer, denoting the minimum number of flight points.

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

Explanation of Sample 1

An optimal plan is to build flight points on trees $2$ and $5$. The table below shows one feasible movement plan for each night sparrow:

$$\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}$$

It can be proven that there is no better solution.

---

Constraints and Notes

$$\def\arraystretch{1.6} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Property} & \textbf{Score} \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}$$

• Special Property A: $\min(h_i) > t$.
• Special Property B: $t > n$ and $h_i \in \{1,t-1,t+1\}$.

For $100\%$ of the testdata, $1 \le n,m \le 5 \times 10^6$, $1 \le h_i,t \le 10^9$, $1 \le p_i \le n$. It is guaranteed that all $p$ are pairwise distinct, and $\max(h_i) > t$.

---

Hint

Obviously, you can take all positions as flight points, and then at moment $1$ let all night sparrows fly to a tree with $h_i > t$, obtaining a valid solution with answer $n$. Therefore, this problem always has a solution.

Translated by ChatGPT 5