Background

Related multiple-choice / true-false problem: https://ti.luogu.com.cn/problemset/1146.

Problem Description

You have $10^9$ cowsheds lined up from left to right. You want to place $n$ cows into the cowsheds. The troublesome part is that your cows are very aggressive: if there are other cows nearby, they will get restless and start trouble. For cow $i$, its attack range is $(a_i, b_i)$, which means that if there is any other cow within $a_i$ cowsheds to its left or within $b_i$ cowsheds to its right, it will start trouble.

You want to keep a continuous segment of cowsheds and sell all the other cowsheds. What is the minimum number of cowsheds you must keep to ensure that there exists at least one way to place all $n$ cows into the remaining cowsheds such that no cow will start trouble?

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers $a_1, a_2, \dots a_n$.
The third line contains $n$ positive integers $b_1, b_2, \dots b_n$.

Output Format

Output one line with one integer representing the answer.

2
1 2
1 2

4

3
1 2 3
3 2 1

7

Hint

Sample 1 Explanation

Keep cowsheds $1, 2, 3, 4$, and place two cows in cowsheds $1$ and $4$, respectively.

Constraints

• For $20\%$ of the testdata, $n = 2$ is guaranteed.
• For another $20\%$ of the testdata, $n = 3$ is guaranteed.
• For $80\%$ of the testdata, $n \leq 8$ is guaranteed.
• For all testdata, $1 \leq n \leq 9$, $1 \leq a_i, b_i \leq 10^3$ are guaranteed.

Translated by ChatGPT 5