Longest Beautiful Subsequence Query

You are given a permutation \( b \) of length \( m \) and a sequence \( a \) of length \( n \). We say that a sequence \( S \) is a beautiful sequence if the elements of \( S \) (in left‐to‐right order) match a contiguous segment of \( b \) (also in left‐to‐right order). In other words, if there exists some index \( i \) (with \( 1\le i\le m \)) and some length \( L \ge 1 \) such that \( S = (b_i, b_{i+1}, \ldots, b_{i+L-1}) \), then \( S \) is beautiful.

You will be given \( q \) queries. Each query consists of two integers \( l \) and \( r \). For each query, consider the subarray \( a[l, r] \) (1-indexed). Your task is to find the maximum length of any subsequence (not necessarily contiguous) of \( a[l, r] \) that forms a beautiful sequence.

Note: The subsequence must preserve the original order from \( a \) and the matched contiguous segment in \( b \) must have consecutive elements. All formulas in this problem are rendered in \( \LaTeX \) format.

inputFormat

The first line contains two integers \( m \) and \( n \).

The second line contains \( m \) integers representing the permutation \( b \).

The third line contains \( n \) integers representing the sequence \( a \).

The fourth line contains an integer \( q \), the number of queries.

Each of the next \( q \) lines contains two integers \( l \) and \( r \) (1-indexed), describing a query.

outputFormat

For each query, output a single integer on a separate line: the maximum length of a beautiful subsequence that can be extracted from the subarray \( a[l, r] \).

sample

3 5
1 2 3
2 1 2 3 2
3
1 5
1 3
2 5

3
2
3