Pęd piłki#234

Pęd piłki

1 sekunda

256 megabajtów

Średnie

Mamy $n$ piłek baseballowych i $n$ maszyn do ich obsługi. Każda piłka ma swoją wagę $w_{i}$ w_i, a każda maszyna ma swoją moc obsługi $p_{i}$ p_i. Możemy wybrać piłkę i maszynę do jej obsługi. Powiedzmy, że trudność złapania $i$ -tej piłki obsługiwanej za pomocą maszyny $j$ wynosi $w_{i} \times p_{j}$ w_i \times p_j. Chcemy wybrać parę ( $i; j$ ) taką, że każda inna para ( $i^{'}; j^{'}$ i';j') ( $i \neq = i^{'}$ i \neq i' i $j \neq = j^{'}$ j \neq j') ma trudność złapania mniejszą lub równą trudności złapania pary ( $i; j$ ). Podaj liczbę takich par.

Dane wejściowe

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — liczbę piłek i maszyn do obsługi.

Druga linia wejścia zawiera $n$ liczb całkowitych $w_{i}$ w_i ( $1 \leq w_{i} \leq 1 0^{9}$ 1 \le w_i \le 10^9) — wagi piłek.

Trzecia linia wejścia zawiera $n$ liczb całkowitych $p_{i}$ p_i ( $1 \leq p_{i} \leq 1 0^{9}$ 1 \le p_i \le 10^9) — moce maszyn do obsługi.

Dane wyjściowe

Wypisz jedną liczbę całkowitą — odpowiedź na problem.

Przykłady

Przykład 1

Loading

Przykład 2

Loading

Punktacja

( $7$ punktów): $n \leq 3$ n \le 3;
( $7$ punktów): wszystkie $w_{i}$ w_i są równe i wszystkie $p_{i}$ p_i są równe;
( $8$ punktów): wszystkie $w_{i}$ w_i są równe;
( $9$ punktów): $w_{i}, p_{i} \leq 1000$ w_i,p_i \le 1000;
( $23$ punkty): $n \leq 100$ n \le 100
( $24$ punkty): $n \leq 1000$ n \le 1000
( $22$ punktów): brak dodatkowych ograniczeń.

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