G. Transformable Segment
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At Narxoz University, the algorithms professor gave the students another puzzle. He wrote an array $$$A$$$ of length $$$n$$$ on the board, and also gave them an array $$$B$$$ of length $$$m$$$, which is called the reference sequence.

The students can apply the following specific cleaning operation to segments of array $$$A$$$:

  • While the length of the current segment is greater than $$$m$$$, it is allowed to choose a position $$$i$$$ ($$$L \le i \lt R$$$) and delete the element $$$A_i$$$, but only if $$$A_i \ne A_{i+1}$$$.

The professor wants to know: how many segments $$$A[L..R]$$$ are there that can be cleaned so that the resulting array is $$$B$$$?

Help the Narxoz students solve the problem and earn an extra point on the exam!

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 100$$$, $$$m \le n$$$) — the lengths of arrays $$$A$$$ and $$$B$$$.

The second line contains $$$n$$$ integers $$$A_1, A_2, \dots, A_n$$$ ($$$1 \le A_i \le 10^9$$$).

The third line contains $$$m$$$ integers $$$B_1, B_2, \dots, B_m$$$ ($$$1 \le B_i \le 10^9$$$).

Output

Print a single integer — the number of segments of array $$$A$$$ that can be transformed into array $$$B$$$ using the described operation.

Example
Input
3 2
1 1 2
1 2
Output
2