Імпульс м'ячей#234

Імпульс м'ячей

1 секунда

256 мегабайтів

Середня

Є $n$ м'ячів для бейсболу та $n$ машин для подачі м'ячів. Кожен м'яч має свою вагу $w_{i}$ w_i, а кожна машина має свою силу подачі $p_{i}$ p_i. Ми можемо вибрати м'яч та машину для подачі м'яча. Скажімо, що складність ловлі $i$ -го м'яча, поданого за допомогою машини $j$ , дорівнює $w_{i} \times p_{j}$ w_i \times p_j. Вам потрібно вибрати пару ( $i; j$ ) таку, що будь-яка інша пара ( $i^{'}; j^{'}$ i';j') ( $i \neq = i^{'}$ i \neq i' та $j \neq = j^{'}$ j \neq j') має складність ловлі меншу або рівну складності ловлі пари ( $i; j$ ). Скажіть кількість таких пар.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — кількість м'ячів та машин для подачі.

Другий рядок містить $n$ цілих чисел $w_{i}$ w_i ( $1 \leq w_{i} \leq 1 0^{9}$ 1 \le w_i \le 10^9) — ваги м'ячів.

Третій рядок містить $n$ цілих чисел $p_{i}$ p_i ( $1 \leq p_{i} \leq 1 0^{9}$ 1 \le p_i \le 10^9) — потужності машин для подачі.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Оцінювання

( $7$ балів): $n \leq 3$ n \le 3;
( $7$ балів): всі $w_{i}$ w_i попарно рівні, всі $p_{i}$ p_i попарно рівні;
( $8$ балів): всі $w_{i}$ w_i рівні;
( $9$ балів): $w_{i}, p_{i} \leq 1000$ w_i,p_i \le 1000;
( $23$ бали): $n \leq 100$ n \le 100
( $24$ бали): $n \leq 1000$ n \le 1000
( $22$ бали): без додаткових обмежень.

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