Polycarpus enjoys studying Berland hieroglyphs. Once Polycarp got hold of two ancient…
- User
Polycarpus enjoys studying Berland hieroglyphs. Once Polycarp got hold of two ancient Berland pictures, on each of which was drawn a circle of hieroglyphs. We know that no hieroglyph occurs twice in either the first or the second circle (but in can occur once in each of them).
Polycarpus wants to save these pictures on his laptop, but the problem is, laptops do not allow to write hieroglyphs circles. So Polycarp had to break each circle and write down all of its hieroglyphs in a clockwise order in one line. A line obtained from the first circle will be called a, and the line obtained from the second one will be called b.
There are quite many ways to break hieroglyphic circles, so Polycarpus chooses the method, that makes the length of the largest substring of string a, which occurs as a subsequence in string b, maximum.
Help Polycarpus — find the maximum possible length of the desired substring (subsequence) if the first and the second circles are broken optimally.
The length of string s is the number of characters in it. If we denote the length of string s as |s|, we can write the string as s = s1s2... s|s|.
A substring of s is a non-empty string x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|). For example, "code" and "force" are substrings of "codeforces", while "coders" is not.
A subsequence of s is a non-empty string y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|). For example, "coders" is a subsequence of "codeforces". Input
The first line contains two integers la and lb (1 ≤ la, lb ≤ 1000000) — the number of hieroglyphs in the first and second circles, respectively.
Below, due to difficulties with encoding of Berland hieroglyphs, they are given as integers from 1 to 106.
The second line contains la integers — the hieroglyphs in the first picture, in the clockwise order, starting with one of them.
The third line contains lb integers — the hieroglyphs in the second picture, in the clockwise order, starting with one of them.
It is guaranteed that the first circle doesn't contain a hieroglyph, which occurs twice. The second circle also has this property.
Output
Print a single number — the maximum length of the common substring and subsequence. If at any way of breaking the circles it does not exist, print 0.
Examples
Input
5 4 1 2 3 4 5 1 3 5 6
Output
2
Input
4 6 1 3 5 2 1 2 3 4 5 6
Output
3
Input
3 3 1 2 3 3 2 1
Output
2
Note
In the first test Polycarpus picks a string that consists of hieroglyphs 5 and 1, and in the second sample — from hieroglyphs 1, 3 and 5.
Assistant
We are given two circular sequences (no duplicate within each sequence). We can break each circle at any point (i.e., choose a starting point) to obtain a linear string a of length la (the hieroglyphs from the first circle in clockwise order starting from that point) and a linear string b of length lb (from the second circle). The goal: maximize the length L of the largest substring of a that occurs as a subsequence in b. Over all choices of breakpoints (i.e., all rotations of the two circles) we want the maximum possible L such that there exists a substring of a (contiguous) that appears as a subsequence (not necessarily contiguous) in b.
We need to compute maximum L.
Observations:
-
Since there are no duplicates within each circle, each value appears at most once in a, and at most once in b. But values can appear in both circles.
-
The circles are given as lists of distinct numbers.
We can think of a rotation of the first circle yields an array a (length la) that is a cyclic shift of the original order. Similarly b is a cyclic shift of the second order. So essentially we can consider all possible alignments of the two cycles. But note we can independently rotate a and b arbitrarily.
Goal: maximize over all rotations of A and rotations of B, the maximal length L of a substring of rotated A that is a subsequence of rotated B.
Equivalently, we want the maximum length of a sequence that is a contiguous segment in some rotation of A and at the same time a subsequence of some rotation of B. But since both rotations are free, we can think of picking any contiguous segment from the cycle A (considering wrap-around) and any subsequence from the cycle B (which may also be taken from a rotation). However, the subsequence must respect order from the rotated B.
We can think of B's rotation as arbitrary, so we can essentially think of B as any cyclic shift of the original list, but the subsequence condition cares about order. So we can consider B as a linear string after rotation, and we can choose that rotation arbitrarily.
Thus we can rephrase: we have two circular sequences A (length n) and B (length m). We can rotate each arbitrarily. Then we want max L such that there exists a string of length L that is a contiguous substring of rotated A and also appears as a subsequence of rotated B.
Since both rotations are arbitrary, this is like: we can pick any cyclic substring of A (i.e., a contiguous block of elements in the circular sense) and any cyclic order of B, and ask whether that substring (as a sequence) can be found as a subsequence of that order of B. We can align the rotations.
But note the substring in A is contiguous and appears exactly in that order. We need to embed it as subsequence in B (preserving order). Since B can be rotated arbitrarily, we can effectively treat B as a circular string and we can choose a starting point such that the subsequence (with order) is found as a subsequence of the linearization starting there. Since B is circular, we can wrap around, but subsequence must respect the order of B after rotation, and cannot wrap around arbitrarily? Actually, if we rotate B, we get a linear string, and subsequence is taken from that linear string. Since we can also consider any rotation, we can treat B as any linearization. So we can choose any starting point for B as well.
Thus, given A and B as cycles, we want the maximum length L such that there exists a contiguous segment (cyclic) of A of length L and a rotation of B in which that segment is a subsequence.
Since both cycles have distinct elements per cycle, each value appears at most once in each cycle.
Let's denote the positions in A: indices 0..n-1 with values A_i (distinct). Similarly B_j.
We need to find max L with the property: There exists a rotation of A (i.e., an index startA) and a rotation of B (startB) such that the substring of length L starting at startA (with indices modulo n) is a subsequence of the rotated B (which is B starting at startB then wrapping around).
We can also think of mapping: For each value x that appears in both A and B, we know its position in A (unique) and its position in B (unique). For values that are only in one cycle, they don't help for common subsequence.
Since we need a substring of A (contiguous block in the cyclic sense) to be a subsequence of B, the order of values in that substring must match an increasing sequence of positions in B (after rotation). However, since B is rotated arbitrarily, we can treat positions cyclically. So we can define an ordering on the circle: For a chosen rotation of B (i.e., a starting point), we assign each element a "linear" coordinate from 0 to m-1 (its index in the rotated order). But we can also think of mapping A values to their positions in B (if present). Then, after rotating B by some offset, the linear order of B positions is shifted. So the mapped positions of A values become (pos_B(x) - offset) mod m, and then we consider these as numbers in [0,m-1] with the natural order? Actually, after rotation, the new order is: we list B starting at offset, then wrap. So the new linear index of a value x that appears at original B index p is (p - offset) mod m, but careful: If we set rotation startB, then the linear order from 0 to m-1 corresponds to B indices: startB, startB+1,...,m-1,0,...,startB-1. So the new index of element originally at index p is: (p - startB + m) % m. That is a number from 0 to m-1.
Thus, for a fixed startB, each value x gets a linear position pos'(x) = (p - startB mod m). For the substring in A (which is a contiguous block in the rotated A) we have a sequence of values x1, x2, ..., xL. For this to be a subsequence in B (in the rotated order), there must exist indices i1 < i2 < ... < iL such that B'[i_k] = x_k. Since each value appears at most once in B, that is equivalent to requiring that the positions pos'(x_k) are strictly increasing in k (since we can take the subsequence exactly as those positions, because each x appears exactly once; but we might skip some? For subsequence, we need an increasing sequence of indices. Since each x appears exactly once, the only possible index for x is its position pos'(x). So the sequence of values x_k can be a subsequence of B' if and only if pos'(x_1) < pos'(x_2) < ... < pos'(x_L). Because we need to pick exactly those positions. There is no alternative since each value appears exactly once. So the condition reduces to: after applying rotation startB, the positions (pos'(x)) of the values in the A-substring must be strictly increasing.
Thus the problem becomes: We have two cycles A (size n) and B (size m). For each common value x (in both), we have its index in A (a_x) and its index in B (b_x). For each choice of rotation of A (starting index startA) and rotation of B (startB), we consider the substring of A of length L starting at startA (cyclic). Let its values be x_1, x_2, ..., x_L (in order). Then we need ( (b_{x_k} - startB) mod m ) to be strictly increasing with k. We want max L.
We can optimize over startA and startB to maximize the longest contiguous segment of A (starting at startA) such that the mapped positions (relative to startB) are increasing.
Alternatively, we can think of fixing startA, and then we need to find startB that maximizes the length of longest increasing subsequence (LIS) of these mapped positions for the cyclic substring? But the substring is contiguous; we need the entire substring to be increasing. Not LIS of arbitrary subset; we need that the contiguous block itself, taken as whole, is increasing in the mapped positions. So for a given startA and startB, the substring length L is the maximum length of a contiguous block (starting at startA? Actually we can choose any contiguous block, not necessarily starting at startA; we can choose any substring of rotated A. But we are free to rotate A arbitrarily, so effectively we can choose any cyclic substring of A. So for a fixed startB, the condition for a particular cyclic substring (contiguous segment) to be good is that the mapped positions (relative to startB) are increasing.
Thus, we can ask: For a fixed startB, consider the array of positions of A values after mapping: For each index i in A (0..n-1) (with its value x_i), define p_i = (b_{x_i} - startB mod m) if x_i appears in B; else p_i undefined (or we can treat as not usable). Then, a substring (contiguous) of A (cyclic) is good if for all consecutive indices in that substring, the p_i are defined and strictly increasing. Actually, we need increasing across the substring, i.e., p_{i} < p_{i+1} < ... . Since the substring length L requires strictly increasing p's. However, we also can skip? Wait: For the substring to be a subsequence, we require p_{i1} < p_{i2} < ... < p_{iL}. For a contiguous substring, the indices are consecutive. The condition is that p_i for those consecutive indices is strictly increasing. That's the necessary and sufficient condition? Because we need to take each value exactly in that order, and each appears at its p_i. For it to be a subsequence, we need p_{i} < p_{i+1}. If p_i < p_{i+1} holds for all consecutive pairs in the substring, then by transitivity, p_i < p_j for i<j. So the whole substring works. If any adjacent pair is not increasing, the sequence is not increasing, thus cannot be a subsequence (since we cannot reorder or skip within the substring, because we must include all values in order. Could we skip some values in B? The substring must appear as subsequence, meaning we pick a sequence of positions in B that match the substring in order. But the substring includes every value in the substring; each value appears exactly once in B at its p_i. So we must include all those positions. If the p_i are not increasing, we cannot have them in increasing order, because we cannot change the order. So yes, the entire sequence of positions must be increasing. Therefore contiguous substring is good iff p_i < p_{i+1} for all consecutive indices in it.
But careful: Since A is a cycle, we have to consider substrings that may wrap around. So we can either duplicate A to handle wrap or treat it cyclically.
Thus, for a fixed startB, we need to find the longest contiguous segment (cyclic) in A such that the mapped positions p_i are strictly increasing. Since we can also rotate A arbitrarily, but rotating A is equivalent to shifting the array A. Since we are free to choose both rotations, effectively we can consider all possible startA and startB. So we could try to fix startB and then compute for the array A (cyclic) the longest run where p_i is increasing; then maximize over startB. But startB changes p_i values (since we subtract startB modulo m). So we need to consider all possible startB.
But note that startB only affects p_i as a cyclic shift of the original b positions modulo m. So if we define q_i = b_{x_i} (original B index) modulo m. Then p_i = (q_i - startB) mod m. The order relation p_i < p_{i+1} after modulo shift is tricky because the values are in [0, m-1] but the order is the natural order on integers, not cyclic order. However, because we performed a shift, we are effectively renumbering the B indices linearly from startB. So the condition p_i < p_{i+1} is with respect to these linear numbers 0..m-1.
Now, the values q_i are fixed. For a given startB, the condition becomes ((q_i - startB) mod m) < ((q_{i+1} - startB) mod m). This is equivalent to something about circular order relative to startB. Let's think: For two numbers q_i and q_{i+1} (in 0..m-1), consider the difference d = (q_{i+1} - q_i) mod m (i.e., the clockwise distance from q_i to q_{i+1}). Then the condition ((q_i - s) mod m) < ((q_{i+1} - s) mod m) is equivalent to: s not lying in the interval (q_i, q_{i+1}] in circular sense? Let's analyze.
We can think of mapping the circle to real line by cutting at s. After subtracting s and taking mod m, we map each original index r to (r - s) mod m, which lies in [0, m-1]. The ordering of these transformed values corresponds to the circular order starting from s. So (r1 - s) mod m < (r2 - s) mod m iff r1 appears before r2 when traversing clockwise from s (strictly). More precisely, if we go clockwise from s, we encounter r1 before r2, and r1 != r2. So condition p_i < p_{i+1} means that when traveling clockwise from startB, we encounter q_i before q_{i+1}. That is, the circular order starting at startB has q_i then later q_{i+1}. This is equivalent to startB not lying in the open arc from q_i to q_{i+1} in clockwise direction? Let's define: For distinct points on a circle, we can say that going clockwise from startB, we see q_i then q_{i+1} if and only if startB is in the arc (q_{i+1}, q_i] going counterclockwise? Actually easier: Consider the circle cut at startB. Then the linear order is the clockwise order from startB. So q_i < q_{i+1} in this linearization if and only if the clockwise distance from startB to q_i is less than to q_{i+1}. Another way: Condition holds iff (q_{i+1} - startB) mod m > (q_i - startB) mod m. Since both are in [0,m-1], this inequality is equivalent to not having startB lie strictly between q_i and q_{i+1} in clockwise order? Let's examine.
Define function f(r) = (r - startB) mod m. This is essentially the distance clockwise from startB to r (if we measure in steps). Then f(r) is in [0,m-1]. f(r1) < f(r2) iff r1 appears before r2 when going clockwise from startB. So condition means q_i appears before q_{i+1} when going clockwise from startB. That is, if we traverse from startB clockwise, we hit q_i first, then later q_{i+1}. This can be characterized: The clockwise arc from startB to q_i does not contain q_{i+1}, or equivalently, the clockwise arc from q_i to q_{i+1} does not contain startB. Because if startB lies strictly between q_i and q_{i+1} clockwise, then starting at startB, you'd encounter q_{i+1} first (since you go clockwise from startB, you'll hit q_{i+1} before coming to q_i). More formally, let’s define the cyclic order. Let’s assume we have points on circle. The condition "q_i appears before q_{i+1} in clockwise order from startB" is equivalent to that startB is not in the open arc (q_i, q_{i+1}) clockwise (i.e., the arc from q_i exclusively to q_{i+1} exclusively going clockwise). If startB equals q_i or q_{i+1}, it's a bit degenerate: but since startB is a position and q_i are positions; if startB equals q_i, then f(q_i)=0, and f(q_{i+1}) >0 unless q_{i+1}=q_i which cannot happen as distinct. So condition holds if startB = q_i? Actually if startB = q_i, then f(q_i)=0, f(q_{i+1})>0, so condition holds. Similarly if startB = q_{i+1}, then f(q_i) = (q_i - q_{i+1}) mod m which is >0 (since q_i ≠ q_{i+1}), and f(q_{i+1})=0, so 0 < something? Actually f(q_{i+1})=0, f(q_i)>0, so f(q_i) > f(q_{i+1})? Wait careful: If startB = q_{i+1}, then f(q_{i+1})=0, f(q_i) = (q_i - q_{i+1}) mod m which is positive (if q_i != q_{i+1}), so we get f(q_i) > f(q_{i+1}) meaning f(q_i) > f(q_{i+1}) so the inequality p_i < p_{i+1} becomes false because p_i > p_{i+1}. So condition fails if startB = q_{i+1}. So startB being exactly q_{i+1} fails, but startB being exactly q_i succeeds. So the condition can be expressed: p_i < p_{i+1} iff startB is not in the half-open arc (q_i, q_{i+1}] clockwise (i.e., the arc that goes from q_i (exclusive) to q_{i+1} (inclusive) moving clockwise). Let's test: if startB is in (q_i, q_{i+1}) clockwise, then from startB, q_{i+1} appears before q_i, so condition fails. If startB = q_{i+1}, then f(q_i) > f(q_{i+1}) => fails. If startB = q_i, then passes. So indeed condition holds iff startB ∈ [q_i, q_i]? Actually exactly when startB is in the closed arc [q_{i+1}, q_i] going counterclockwise? Better to avoid confusion.
Thus for each adjacent pair (i,i+1) in A (cyclic), we have a condition on startB for which p_i < p_{i+1}. Since A is circular, we have n adjacent pairs (including wrap from last to first). For each such pair, we can define the set of startB values (i.e., rotations of B) that make that pair increasing. The condition for a whole contiguous block of A to be good is that for all consecutive pairs in that block, the condition holds (i.e., startB belongs to intersection of those sets). Then we want to find a maximal length L such that there exists a contiguous block (cyclic) of length L and a startB that lies in the intersection of conditions for all its internal adjacent pairs.
But we also need that all values in the substring appear in B; if some value in A does not appear in B, then p_i is undefined, and that substring cannot be used because the subsequence can't include a value not in B. So we need all values in the substring to be common (present in both circles). Since each value appears at most once in each, for those common values we have q_i defined; for values not common, we cannot include them in the substring (as subsequence can't have values not in B). So the substring must consist entirely of values that are present in B. Therefore we only care about common elements. But we have to consider that A may contain elements not in B, which break continuity. So we can think of A as a cyclic string where each position is either "good" (value in B) or "bad" (value not in B). Then we want a contiguous block (cyclic) consisting only of good positions, such that there exists a startB making the increasing condition hold for all consecutive pairs in that block.
Now, note that startB is a single integer from 0 to m-1 (the rotation offset). So we need to find the maximum length of a contiguous block of good positions in A for which the intersection of the allowed startB sets (over all internal adjacent pairs) is non-empty. And we can also consider that the block can start anywhere (so we can choose the block) and we can also choose startB accordingly.
Thus, we can treat each adjacent pair (between consecutive good positions? Actually the block includes positions that are consecutive in A. The condition for each adjacent pair within the block (i.e., between index i and i+1 in A) depends only on the two values A_i and A_{i+1} (both good). So we have constraints: startB ∈ S_{i} where S_i is the set of startB values such that (b_{A_{i+1}} - startB) mod m > (b_{A_i} - startB) mod m, i.e., such that A_i appears before A_{i+1} when traversing clockwise from startB. Or equivalently, startB must not be in the half-open arc (b_{A_i}, b_{A_{i+1}}] clockwise.
Now, the sets S_i are arcs (or complements of arcs) on the circle of m positions. Specifically, S_i = all startB such that when we go clockwise from startB, we meet A_i before A_{i+1}. This is a set of m positions (the whole circle) minus a forbidden interval (maybe of length something). Since the circle is discrete with m positions (0..m-1), but values are indices; all distinct. For two distinct positions p = b_{A_i} and q = b_{A_{i+1}}, the condition startB ∈ S_i is equivalent to startB not in the set of positions that would cause q to appear before p. As argued, that set is: the half-open clockwise interval (p, q] (i.e., positions strictly after p (clockwise) up to and including q). Let's verify with examples.
Take m=10. p=2, q=5. Clockwise from startB: if startB = 2, then p is at 0, q at 3 -> p before q. Good. startB=3: then p at (2-3 mod10)=9, q at (5-3)=2 -> p=9, q=2 => p > q, so p after q, not good. For startB=4: p=8, q=1 => p>q, not good. startB=5: p=7, q=0 => p>q, not good. startB=6: p=6, q=9? Actually (2-6 mod10)=6, (5-6 mod10)=9 -> p=6, q=9 => p<q, good. So indeed good startB are those not in (2,5] i.e., 3,4,5 are bad; 2,6,7,8,9,0,1 are good. That's the complement of the clockwise interval from p exclusive to q inclusive. So S_i = circle \ (p, q] clockwise.
Thus S_i is a set of size m - d, where d is clockwise distance from p to q inclusive of q but exclusive of p? Actually the number of positions in (p, q] clockwise is the number of steps from p+1 to q modulo m. That distance is ( (q - p + m) % m ). Since q != p, that distance is between 1 and m-1. So size of S_i = m - ((q-p+m) % m). Which is the clockwise distance from q to p (i.e., the other arc). So S_i is actually the arc starting from q and going clockwise to p inclusive (including p, excluding q? Let's see: The good set is [q+1, p]? Actually complement of (p, q] is the set of positions from q+1 to p (inclusive) in clockwise order. Because going clockwise, after q you wrap to q+1, then eventually up to p. So S_i is the closed arc from q+1 to p (including both ends if we consider discrete positions). For example p=2, q=5, good positions: 6,7,8,9,0,1,2. That's from q+1=6 to p=2 wrapping around. So yes, S_i = {startB | startB in [q+1, p] modulo m} (including endpoints). But note that p is included, q+1 is included? q+1 is 6, so yes includes 6,7,8,9,0,1,2. That set size = ( (p - (q+1) + m) % m ) + 1 = ( (2-6+10) %10 ) +1 = (6) +1? Actually (2-6+10)=6, mod10=6, +1 =7, which is m - ((q-p+10)%10) = 10 - 3 =7. Good.
Thus S_i is a contiguous arc on the circle (in the cyclic sense). It's possibly the whole circle if the distance is 1? Actually if q is immediately after p clockwise, i.e., (q-p+m)%m =1, then (p, q] includes only q. So forbidden set size =1, S_i size = m-1, which is an arc of length m-1 (since complement of a single point is not a contiguous arc? Actually on a discrete circle, complement of a single point is not a contiguous arc if we require contiguity wrapping around? It is contiguous if we allow wrap: it's all points except one, which can be considered as an arc that starts at q+1 and goes all the way to p, which includes all points except q. That is contiguous if we consider the circle: starting at q+1, go clockwise, you'll pass through all points except q until you reach p. That's a contiguous arc of length m-1. So yes, it's contiguous because the circle is a cycle; an arc can be defined as a set of consecutive positions modulo m. So S_i is always a contiguous arc (including possibly the whole circle if the forbidden set empty? but forbidden set always non-empty? Actually if p and q are distinct, the forbidden set (p, q] has size at least 1. So S_i size is at most m-1, at minimum? Minimum when forbidden set size is m-1, i.e., when (q-p+m)%m = m-1, then S_i size = 1, meaning only one startB works: that is when startB = q+1? Actually if distance from p to q clockwise is m-1, that means q is just before p clockwise (since p to q clockwise is almost full circle, q is one step before p). Then forbidden set (p, q] is everything except p? Let's test: m=5, p=2, q=1 (since (1-2+5)%5=4). Forbidden (2,1] clockwise means from 2 exclusive to 1 inclusive: positions 3,4,0,1. Forbidden size 4, S_i = complement = {2} only. So indeed S_i can be a single point.
Thus each constraint is a requirement that startB must lie in a specific arc (contiguous on the circle). The intersection of multiple such arcs is also an arc (or empty). So for any contiguous block of good positions in A, we need the intersection over its internal arcs to be non-empty. We want the longest such block.
Since we can choose both block and startB, we can think: For each possible startB, we can consider the arcs that are satisfied. For a fixed startB, which adjacent pairs are increasing? Those where startB ∈ S_i. So for fixed startB, we can compute the length of the longest contiguous segment in A (cyclic) consisting only of good positions such that each internal adjacent pair satisfies the increasing condition. That is essentially the longest run where all constraints hold for that startB. Then the answer is the maximum over startB of that length. Because for each startB we can also rotate A arbitrarily? Actually we already accounted for rotating A by choosing the starting point of the block. Since A is a cycle, we can choose any contiguous block (cyclic). For fixed startB, we can compute the maximal length of a cyclic contiguous block of A (consisting only of good positions) such that each consecutive pair (in that block) is increasing under that startB. That's essentially the longest "valid" contiguous segment in A under that startB. Since we can also rotate A arbitrarily (choose any startA), this is equivalent to scanning the cyclic array for the longest run of positions that satisfy the increasing condition between neighbors. So we can fix startB, then evaluate the longest run of indices i (cyclic) where for each step from i to i+1 (mod n) we have startB ∈ S_{i} and both positions are good. Actually careful: For a block of length L, we need L positions i, i+1, ..., i+L-1 (cyclic) such that for each adjacent pair (j, j+1) within the block (i.e., from i to i+1, i+1 to i+2, ..., i+L-2 to i+L-1), startB ∈ S_{j} (i.e., the condition holds). Also all these positions must be good (value present in B). Note that if a position is bad, it cannot be part of the block.
Thus for each startB, we can mark each edge (between consecutive A positions) as "good edge" if startB ∈ S_{edge} (i.e., the increasing condition holds) and also both vertices are good (since if either endpoint is bad, edge can't be used, but we can still have block of length 1? For length 1 block, there are no edges, so condition vacuously true. So single good positions are always valid (since any single element can be a subsequence? Actually we need substring of A of length 1 to be subsequence in B. That's possible if that element is in B. So yes, L=1 is possible if element common). So we consider vertices that are good. And edges that are good (both endpoints good and startB satisfies the increasing condition). Then the maximal valid block corresponds to the longest cyclic path of consecutive vertices where all edges between them are good (i.e., a maximal contiguous segment of good vertices where all connecting edges are good). That's like we have a binary string on vertices (good/bad) and binary on edges (good/bad). The valid block is a contiguous segment of vertices such that all vertices are good and all internal edges are good. So we want the longest such segment.
Thus, for each startB, we can compute the maximum length of a consecutive (cyclic) run of good vertices where all intervening edges are good. That is easy: we can iterate through the cyclic order of A (2n maybe) and compute runs.
Now we need to consider all possible startB (0..m-1). There can be up to 10^6 possible startB (since m up to 10^6). That might be feasible if we can efficiently compute for each startB the runs. However, we can't iterate over all m and for each recompute all edges condition from scratch (which would be O(m * n) impossible). We need a smarter way.
Observation: The condition for an edge (i,i+1) being good depends on whether startB lies in the arc S_i. S_i is a contiguous arc on the circle of B positions. So as startB varies, each edge toggles between good and bad depending on startB's position relative to the arc. So we have n edges (or fewer, because some edges involve a bad vertex; but if either endpoint is bad, that edge is always bad, since block cannot cross a bad vertex; but we can treat those as always bad, regardless of startB). Actually if an edge connects a good and a bad, then it cannot be part of a valid block, because a block must consist solely of good vertices. So such edges are irrelevant; they break the runs. So we only care about edges where both endpoints are good (i.e., both values appear in B). For such edges, we have an associated arc S_i (the set of startB for which the edge is good). For startB not in S_i, the edge is bad.
Thus we have a set of constraints (edges) each with an allowed interval (arc) on the circle of startB. We need to find startB that maximizes the length of the longest run of consecutive vertices (in A) where all edges within the run are allowed for that startB.
Because A is a cycle, the vertices are arranged in a circle. For each startB, we essentially have a labeling of edges (good/bad). We want the longest cyclic segment of vertices with all edges inside good.
This is reminiscent of problems where we have a circular array and each position (edge) has a condition that is an interval on a parameter, and we need to maximize over the parameter the longest contiguous stretch where all conditions are satisfied. Since m up to 10^6 and n up to 10^6, we could perhaps sweep over startB and maintain dynamically which edges are good, and update the maximum run length. Because as startB changes by 1, the status of edges changes only when startB crosses a boundary of an arc S_i. Each edge's condition flips when startB enters or leaves its allowed arc. Since arcs are intervals on a circle, each edge contributes two events (enter and exit). Total number of edges that are "good both vertices" is at most n (but might be less). So total events O(n). We can do a sweep over startB from 0 to m-1, updating the status of edges and recomputing the longest run of vertices where all edges are good. This seems plausible.
But there is a nuance: The arcs are on a circle. We can break the circle at some point and treat startB linearly, but because arcs wrap, we may need to handle wrap-around. However, we can convert to linear by considering startB in [0, m-1] and for arcs that wrap, we can split them into two intervals (like [l, r] with possible wrap). Each edge's allowed set S_i is an arc that may wrap (since it's from q+1 to p inclusive). But more conveniently, we can represent S_i as a set of startB values where condition holds. Since it's contiguous on the circle, it can be represented as one interval modulo m. For sweeping, we can handle by doubling the range or using modular arithmetic.
Alternatively, we can rotate the coordinate system for startB to simplify. Since we can choose any startB, we could fix a reference. But easier: We can perform a sweep on the circle by considering all events sorted by position, then maintaining the status of each edge as we go around. Since the circle is discrete (m up to 1e6), we can process in order from 0 to m-1, and treat wrap-around by processing events accordingly. Because the status of edges is a function on the circle. We want to find the point(s) where the maximum run length is maximized.
But we need to compute, for each startB, the maximum length of a valid block. Updating that efficiently as we change the status of edges might be challenging if we have to recompute runs from scratch. However, we can perhaps precompute the structure of runs based on which edges are active. The graph is just a cycle of vertices (size n) where each edge may be "active" (good) or not. We want the longest consecutive sequence of vertices where all edges between them are active. That is essentially the longest path in the cycle where you traverse consecutive vertices only through active edges. In a cycle of vertices, if we break it at inactive edges, we get segments of vertices where all internal edges are active. The longest such segment length (number of vertices) is the answer for that startB. So for a given startB, we have a set of inactive edges (bad). The active edges are those that satisfy condition. Then the cycle is broken into components (chains) at inactive edges. The maximum component size (number of vertices) is the answer.
Thus, we need to compute, for each startB, the maximum size of a connected component of the cycle when we delete edges that are inactive. Since the graph is a cycle, each component is a contiguous segment (in the cyclic sense) of vertices bounded by inactive edges.
So if we can maintain which edges are active as startB varies, we can maintain the component sizes and the maximum component size. This is like a dynamic graph on a cycle where edges are added/removed as we sweep startB. We need to support edge toggles (activation/deactivation) and maintain the lengths of segments (components) on a circle, and the maximum length. Since the cycle is static (vertices order fixed), and edges are between consecutive vertices (and also the wrap edge between n-1 and 0). Actually A is a cycle: vertices 0..n-1, edges between i and (i+1) mod n. We consider all these n edges. When an edge is inactive, it breaks the cycle. The components are the arcs between inactive edges.
We can model the cycle as a circle with n edges. Initially, we need the status for a given startB. But we will sweep startB from 0 to m-1, and edges will be toggled as we cross boundaries. Since we only have at most n edges that could ever be active (those with both endpoints good). For edges with a bad endpoint, they are always inactive (never part of a component because vertices themselves are bad? Wait, careful: The vertices that are bad cannot be part of any valid block at all. So in our component model, we should consider that only good vertices can be included. If a vertex is bad, it automatically breaks any component: even if edges adjacent to it are active, you cannot include that vertex because it's not good. So the component segmentation must also consider that bad vertices act as barriers. Actually our valid block requires all vertices in the block to be good, and all edges within block to be active. So if a vertex is bad, it cannot be in a block. So the cycle effectively is split at bad vertices as well. So we can pre-mark some vertices as "bad" (value not in B). These are fixed and never change with startB. For those vertices, they are always barriers: no block can cross them. Additionally, edges incident to a bad vertex are automatically not useful because even if the condition would hold, the vertex is bad, so the block cannot extend across that edge. So we can treat the "active" status for an edge as relevant only if both endpoints are good. For edges with at least one bad endpoint, they are always "inactive" in terms of connectivity for good vertices, because they separate good segments. However, they also affect the ability to have a block that includes both sides? Since a block can't include a bad vertex, the block ends at bad vertices. So we can think of the good vertices forming segments on the cycle separated by bad vertices. Within each segment of consecutive good vertices (in the cyclic order), we have edges between them (all those edges connect good vertices). For a block to be within that segment, we need that all edges inside the block are active (i.e., satisfy condition). But also the segment may be broken further by inactive edges (due to condition). So essentially we have a set of good vertices arranged in some maximal segments separated by bad vertices. Within each such maximal good segment, we have edges between consecutive good vertices. These edges may be active or inactive depending on startB. Then the components (maximal contiguous good vertices with all edges active) are subsegments of these good segments, split by inactive edges. So we need to compute, for each startB, the maximum length of a subsegment of good vertices with all internal edges active.
Thus we can preprocess the cycle: Identify the positions of good vertices (those with value in B). The array A is of length n. For each i, we have a flag good[i] = (A[i] in B). For each consecutive pair (i, (i+1) mod n) where both good[i] and good[i+1] are true, we have an edge e_i (between i and i+1). For such edge, we have an allowed set S_i (arc of startB values where it is active). For edges adjacent to a bad vertex, they are always inactive (or rather they are not considered because they separate good segments; we can treat them as always inactive, but they are not part of our dynamic edge set). Also the wrap edge from n-1 to 0 should be considered similarly.
So we have a set E of dynamic edges (good-good edges). There are at most n such edges (but typically less). Each such edge has an arc S_i where it is active. Outside S_i, it is inactive. As we sweep startB, an edge toggles active/inactive at the boundaries of its S_i.
Now the problem reduces to: We have a circular arrangement of good vertices, but actually the overall cycle includes bad vertices which break the circle into linear segments of good vertices. Since bad vertices are fixed, the overall structure is not a single cycle of good vertices; it's several independent linear chains (in a cyclic sense, but because the original A is a cycle, the good vertices might form several arcs on the circle, separated by bad vertices). However, note that the circle is overall cyclic, but if there is at least one bad vertex, then the set of good vertices is not a full cycle; it's a set of disjoint arcs. In each such arc, vertices are consecutive good vertices. The endpoints of these arcs have a bad neighbor (or maybe there are no good vertices at all). Within each arc, edges between consecutive good vertices are the ones we have dynamic status. The arcs themselves are fixed (they don't change with startB). For a given startB, we want the longest subsegment within any of these arcs such that all internal edges are active. That's essentially the longest contiguous run of vertices where all edges between them are active, but also bounded by the ends of the arc.
Thus, we can treat each maximal contiguous segment of good vertices (in the cyclic order) as an independent linear array. For each such segment, we have a sequence of vertices v_1, v_2, ..., v_k (k >=1). There are edges between v_j and v_{j+1} for j=1..k-1. These edges are dynamic. For a given startB, we want the longest contiguous subarray of this segment where all edges within are active. That is analogous to having a binary string on edges (active/inactive), and we want the longest consecutive run of vertices where all connecting edges are 1. This is equivalent to: for each segment, if we denote the edges statuses e_1,...,e_{k-1}, then the maximal run length is 1 + (maximal number of consecutive 1's in the edge status sequence). Because a block of length L corresponds to L vertices, and the edges between them must all be 1. So the longest block length in that segment = 1 + (longest consecutive run of 1's among its edges). Also, if the segment has length k, we also have the possibility of taking the whole segment if all edges are 1, giving length k.
Thus, overall answer for a given startB is max over all good segments of (1 + longest run of consecutive active edges in that segment). Also, if there is a segment of length 1 (k=1), there are no edges, so it contributes length 1 (provided the vertex is good). So answer is at least 1 if any good vertex exists.
Now, since bad vertices are fixed and independent of startB, we can precompute these segments. Then we need to maintain, as startB varies, for each segment, the longest run of consecutive active edges, and take the maximum among segments (plus 1). This is dynamic as edges toggle status.
Since edges are independent but within a segment they are arranged linearly. We need a data structure that supports toggling an edge's state (active/inactive) and querying the maximum run of consecutive 1s over all segments. We have at most n edges total (including all good-good edges). The number of events (status changes) is O(number of edges) because each edge toggles twice (as startB sweeps around the circle). However, we need to sweep startB across m positions, but we only need to evaluate at points where something changes. Since the status only changes at boundaries of arcs, the maximum length might change only at those points. So we can compute the answer at each interval between events and take the maximum.
But careful: The status function for each edge is constant on intervals between event points (boundaries). The maximum answer is the maximum over all startB values. Since startB is discrete (0..m-1), but we can consider continuous; but the arcs are defined on discrete positions. Since we have at most O(n) events, we can process each event and compute answer for each interval. However, the answer function could also change within an interval? Since statuses are constant, the longest run of consecutive active edges within each segment is constant, so answer is constant. So we can evaluate at any representative startB in each interval. Also we need to consider boundaries exactly? Possibly the maximum may occur at a point where startB equals a boundary; but since at boundaries statuses of some edges may be ambiguous (if we define the condition precisely, we need to decide whether startB exactly at the boundary counts as satisfying? The condition for an edge to be active is startB ∈ S_i. S_i includes its endpoints as per definition? We need to be precise about inclusive/exclusive. Recall S_i = set of startB such that (b_{A_i} - startB) mod m < (b_{A_{i+1}} - startB) mod m. Let's re-derive the exact condition for discrete indices. For given p and q (distinct), we want ((p - s) mod m) < ((q - s) mod m). Equivalent to: s not in the half-open arc (p, q] clockwise. So active when s ∈ complement = [q+1, p] modulo m. This is a closed interval on the circle: from q+1 to p inclusive. So endpoints: s = p is allowed, s = q+1 is allowed, s = q is not allowed, s = p+1 is not allowed? Let's check: p=2, q=5, m=10. Allowed s = {6,7,8,9,0,1,2}. So indeed includes 2 (p) and 6 (q+1). So S_i = { s | s ∈ [q+1, p] } (cyclic). So it's a closed interval. That's fine.
Thus the active status changes exactly at s = q+1 and s = p+1? Actually when s moves from p to p+1, it leaves S_i because p+1 is not in [q+1, p]. So the boundary at p+1 is where it becomes inactive. At s = q, it's inactive; at s = q+1, becomes active. So events occur at s = q+1 (enter) and s = p+1 (exit) modulo m. Since we will sweep s from 0 to m-1, we have events at these positions.
Now, we need to handle modulo m. So we can treat s in [0, m-1]. For each edge, we have an interval [L, R] (inclusive) where it is active, which may wrap. We'll convert to linear by possibly splitting into two intervals.
Goal: Compute maximum over s of f(s) = 1 + max_{segments} longest_consecutive_1s_in_edges_of_segment(s). Actually we need to consider also that a block can be of length 1 even if no edges active; that is always possible if there is at least one good vertex. So f(s) is at least 1 if any good vertex exists. So we can compute that base.
We can think of maintaining for each segment the longest run of consecutive active edges. The segments are independent. So we need a data structure that, given a set of edges (each belonging to a specific segment and having a position in that segment's edge list), and updates to toggle active status, can report the global maximum run length (over all segments) quickly. Since we will process O(n) events (each edge toggles twice), and n up to 1e6, we need near O(n log n) or O(n) total.
We can perhaps precompute all segments and within each segment, we could treat the edges as a binary array that changes. Since the events are only toggles (active/inactive), and we need to maintain the longest run of consecutive 1s after each toggle, we could use a segment tree per segment, but there could be many segments (up to n in worst case if alternating good/bad). However, total number of edges is O(n), so total size of all segments is O(n). Using a segment tree per segment might be too heavy if we have many small segments; but we could use a global segment tree over all edges? However edges are arranged in a cycle, but segments are separated by bad vertices, meaning the edges in different segments are independent. The runs we care about are per segment. So we can treat each segment as an independent array of edges (size k-1). We need to support toggle of an edge and query the maximum run of consecutive 1s in that segment. Then we need to keep track of the global maximum across all segments.
Because total number of toggles is O(n), we could recompute the longest run for a segment from scratch after each toggle that affects it? That would be too expensive if a segment has many edges and toggles many times (worst-case each edge toggles twice, and a segment could have O(n) edges, leading to O(n^2) if we recompute each time). So we need a more efficient method.
Alternative approach: Since the arcs for edges are defined on startB, maybe we can compute the answer directly without dynamic maintenance. Perhaps we can think of this as a problem of finding a longest substring of A that can be made increasing in B after rotation, which might be reducible to something like longest contiguous subsequence where the order of b-positions is "consecutive" in terms of cyclic order? Let's explore further.
We have A as a cycle with distinct values, and B as a cycle with distinct values. For a contiguous segment of A (of length L) to be a subsequence of some rotation of B, we need that the b-indices of those values, when considered in the order of the segment, are increasing in the linear order defined by some rotation (i.e., there exists an offset s such that (b_{x_i} - s) mod m is increasing). This is reminiscent of the concept of circular sequences and "circular order". For a fixed segment, we can ask: does there exist an s such that these numbers are increasing? This is equivalent to the segment's b-values being in cyclic order without a "break". More specifically, given a sequence of positions p_1, p_2, ..., p_L (all distinct), there exists an s such that (p_i - s) mod m is increasing iff when you place the points on a circle, they appear in order without wrapping around twice; i.e., the cyclic order of the points is the same as the order of the segment. In other words, if we go around the circle starting at some point, we encounter p_1, p_2, ..., p_L in that order consecutively (without any of the points appearing out of order). That is equivalent to that the sequence p_1, p_2, ..., p_L is a "circularly increasing" sequence, meaning that the circular differences are all positive when considered with appropriate starting point. More formally, there exists s such that (p_i - s) mod m is strictly increasing iff the points p_i are all distinct and the maximum gap (clockwise distance) between consecutive points (in the order of the segment) when placed on the circle is less than the sum of the other gaps? Hmm.
Actually, given a sequence of distinct points on a circle, there exists a rotation that makes them appear in increasing order (as linear sequence) if and only if they are already in circular order (i.e., they appear around the circle in that order without any other point interleaving? Not exactly). For a set of points, we can always choose s to be just before the first point, then the sequence becomes increasing if and only if when we traverse the circle starting from s, we see the points exactly in the order p_1, p_2, ..., p_L, with no other points from the set interspersed? But the set is exactly those points. So condition is that if we list the points in clockwise order starting from some point, we get the sequence p_1, p_2, ..., p_L. That means that the points appear consecutively on the circle in that exact order. In other words, the cyclic order of the points (when sorted by position) must match the order of the segment. This is equivalent to that the positions p_i are already in increasing order modulo m, except possibly with one wrap. More precisely, after rotating the circle appropriately, they become increasing. This is possible iff there is no "break" where the sequence goes backwards in terms of circular order. Another way: The condition (p_i - s) mod m increasing means that if we sort the positions and then consider the order they appear, the segment's order must be either exactly that sorted order or a cyclic shift of it. Because if we start at s just before the smallest (in the transformed sense), then the transformed values are increasing as we go clockwise. So we need the order of the segment to match the circular order of the points when arranged around the circle. That is, if we look at the positions on the circle, the sequence p_1, p_2, ..., p_L should be in clockwise order (i.e., each successive point is reached by moving clockwise from the previous, without going backwards). That is equivalent to that for each i, the clockwise distance from p_i to p_{i+1} is less than the clockwise distance from p_i to any point not in the segment? Actually, we need that when traveling clockwise from p_i, the next point among the set should be p_{i+1}, and so on. So the sequence must be a contiguous arc on the circle in that order. More precisely, the points p_1,...,p_L must appear in clockwise order around the circle, and they must be consecutive in the sense that there are no other points from the set (i.e., from B? But B contains all points, but we are only considering these L points; we don't care about other points from B. The condition only involves these L points; other points in B do not matter because we are only checking that the transformed positions are increasing. If there are other points in between, that's fine because we can skip them (subsequence). Wait: The condition for the substring to be a subsequence of B after rotation is that the transformed positions (p_i - s) mod m are increasing. That does NOT require that there are no other B values between them; subsequence can skip arbitrary elements. So we don't need the points to be consecutive on the circle; we only need their order to be consistent with some rotation, i.e., that we can find an s such that (p_i - s) mod m is increasing. This is equivalent to the sequence p_1,...,p_L being "circularly monotone". Let's examine.
For any distinct numbers p_1,...,p_L, does there always exist an s making (p_i - s) mod m increasing? Not always. For example, m=10, p_1=2, p_2=5, p_3=3. Can we find s such that (2-s) mod10 < (5-s) mod10 < (3-s) mod10? That would require an ordering 2,5,3 after rotation. Since 2<5 but 5<3 would require wrap-around: If we choose s such that after subtracting, the values wrap, we could have something like (2-s) mod10 = 8, (5-s)=1, (3-s)=2? Let's try s=6: (2-6)= -4 mod10=6, (5-6)=-1 mod10=9, (3-6)=-3 mod10=7 -> 6,9,7 not increasing. s=7: (2-7)=-5 mod10=5, (5-7)=-2 mod10=8, (3-7)=-4 mod10=6 -> 5,8,6 not increasing. s=8: (2-8)=-6 mod10=4, (5-8)=-3 mod10=7, (3-8)=-5 mod10=5 -> 4,7,5 not. s=9: 3,6,4 not. s=0: 2,5,3 not. s=1: 1,4,2 not. s=2: 0,3,1 not. s=3: 9,2,0 -> 9,2,0 not increasing (9>2). s=4: 8,1,9 -> 8,1,9 not. s=5: 7,0,8 -> 7,0,8 not. So no s works. So some sequences cannot be made increasing. The condition is that the sequence does not have a "circular inversion". More formally, a sequence of distinct numbers can be made increasing
-