Minimum Length Zigzag Sequence

Given two arrays of length n, denoted by \(a\) and \(b\), we say that a sequence \(p = (p_1, p_2, \ldots, p_m)\) is valid if and only if it satisfies the following conditions:

• \(p_1 = 1\).
• For every \(1 \le i < m\), \(|p_i - p_{i+1}| = 1\) (i.e. the absolute difference between consecutive elements is 1).
• For every \(1 \le k \le n\), there exists an ordered pair of indices \((i, j)\) with \(1 \le i < j \le m\) such that \(p_i = a_k\) and \(p_j = b_k\).

Your task is to compute the minimum possible length \(m\) among all valid sequences \(p\).

Explanation:

Note that the condition \(|p_i - p_{i+1}| = 1\) implies that the sequence represents a walk on the number line with steps of size one.

Observe that for any pair \((a_k, b_k)\) with \(a_k b_k\), the sequence must have a descending segment from \(a_k\) to \(b_k\).

A constructive strategy to achieve the minimum length is as follows:

1. Let upward pairs be those with \(a_k < b_k\) and downward pairs be those with \(a_k > b_k\).
2. Define \(high_{up}\) as the maximum \(b_k\) among upward pairs (if any exist; otherwise, treat it as 1).
3. For downward pairs, note that to have an occurrence of \(a_k\) followed later by \(b_k\), you must first raise the sequence high enough. Hence, define \(high_{down}\) as the maximum \(a_k\) among downward pairs and \(low_{down}\) as the minimum \(b_k\) among downward pairs.
4. Let \(high = \max(high_{up}, high_{down}, 1)\).
5. If there is no downward pair (i.e. all pairs satisfy \(a_k \le b_k\)), an optimal valid sequence is the increasing sequence from 1 to \(high\). Its length is \(high\).
6. If there is at least one downward pair, an optimal valid sequence is to increase from 1 to \(high\) and then decrease from \(high\) down to \(low_{down}\). This sequence is given by: \[ p = (1, 2, \ldots, high, high-1, \ldots, low_{down}) \] and its length is \(\text{length} = high + (high - low_{down})\).

The answer is the minimum possible length \(m\) of such a sequence.

inputFormat

The input consists of three lines:

1. An integer \(n\) (\(1 \le n \le \text{some limit}\)).
2. n space-separated integers representing the array \(a\).
3. n space-separated integers representing the array \(b\).

outputFormat

Output a single integer: the minimum possible length \(m\) of a valid sequence \(p\).

sample

1
1
3

3