Ball momentum#234

Ball momentum

1 second

256 megabytes

Medium

There are $n$ baseball balls and $n$ machines for serving them. Each ball has its weight $w_{i}$ w_i and each machine has its power of serving $p_{i}$ p_i. We can choose a ball and machine to serve it. Let's say that difficulty of catching $i$ -th ball served using machine $j$ is $w_{i} \times p_{j}$ w_i \times p_j. You want to pick a pair ( $i; j$ ) such that any other pair ( $i^{'}; j^{'}$ i';j') ( $i \neq = i^{'}$ i \neq i' and $j \neq = j^{'}$ j \neq j') has difficulty of catching less or equal to the difficulty of catching the pair( $i; j$ ). Tell the number of such pairs.

Input

The first line of input contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — number of balls and serving machines.

The second line of input contains $n$ integers $w_{i}$ w_i ( $1 \leq w_{i} \leq 1 0^{9}$ 1 \le w_i \le 10^9) — weitghts of balls.

The third line of input contains $n$ integers $p_{i}$ p_i ( $1 \leq p_{i} \leq 1 0^{9}$ 1 \le p_i \le 10^9) — powers of serving machines.

Output

Print one integer — answer to the problem.

Examples

Example 1

Loading

Example 2

Loading

Scoring

( $7$ points): $n \leq 3$ n \le 3;
( $7$ points): all $w_{i}$ w_i are equal and all $p_{i}$ p_i are equal;
( $8$ points): all $w_{i}$ w_i are equal;
( $9$ points): $w_{i}, p_{i} \leq 1000$ w_i,p_i \le 1000;
( $23$ points): $n \leq 100$ n \le 100
( $24$ points): $n \leq 1000$ n \le 1000
( $22$ points): no additional restrictions.

w_{i}

p_{i}

w_{i} \times p_{j}

i^{'}; j^{'}

i \neq = i^{'}

j \neq = j^{'}

1 \leq n \leq 2 \cdot 1 0^{5}

w_{i}

1 \leq w_{i} \leq 1 0^{9}

p_{i}

1 \leq p_{i} \leq 1 0^{9}

n \leq 3

w_{i}

p_{i}

w_{i}

w_{i}, p_{i} \leq 1000

n \leq 100

n \leq 1000