Lễ hội Snuke (Snuke Festival)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một bàn thờ được ghép từ đúng ba bộ phận: một bộ phận phía trên, một bộ phận ở giữa và một bộ phận phía dưới.

Có $N$ bộ phận cho mỗi loại. Kích thước của các bộ phận phía trên là $A_1,A_2,\ldots,A_N$, ở giữa là $B_1,B_2,\ldots,B_N$, và phía dưới là $C_1,C_2,\ldots,C_N$.

Một bộ ba chỉ số $(i,j,k)$ tạo thành bàn thờ hợp lệ khi

Hai bàn thờ được xem là khác nhau nếu ít nhất một trong ba bộ phận được chọn khác nhau. Vì vậy, ngay cả khi hai bộ phận có cùng kích thước, chúng vẫn là hai lựa chọn khác nhau nếu chúng có chỉ số khác nhau.

Hãy đếm số bộ ba chỉ số $(i,j,k)$ tạo thành bàn thờ hợp lệ.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $A_1,A_2,\ldots,A_N$.
• Dòng thứ ba chứa $B_1,B_2,\ldots,B_N$.
• Dòng thứ tư chứa $C_1,C_2,\ldots,C_N$.

Output

In số bàn thờ hợp lệ.

Subtask

• Subtask 1 — 20%: $1\le N\le50$.
• Subtask 2 — 30%: $1\le N\le3000$.
• Subtask 3 — 50%: $1\le N\le10^5$, $1\le A_i,B_i,C_i\le10^9$.

Ví dụ

Input

2
1 5
2 4
3 6

Output

3

Giải thích

Ba lựa chọn hợp lệ là $(A_1,B_1,C_1)$, $(A_1,B_1,C_2)$ và $(A_1,B_2,C_2)$. Mỗi lựa chọn đều thỏa $A_i<B_j<C_k$.