FOURPOS - Bốn hoán vị

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho số nguyên dương n và 4 dãy số a,b,c,d đều là các hoán vị của dãy 1,2,…,N.

Tìm tất cả các cặp số u,v thỏa mãn đồng thời:

Trong a, u đứng trước v

Trong c, u đứng trước v

Trong b, u đứng sau v

Trong d, u đứng sau v

Giới hạn:

1 <= N <= 100000.

Lưu ý kết quả nằm trong khoảng int64 của pascal, long long của C++.

Input

Dòng 1: Số nguyên dương n

Dòng 2: n số miêu tả dãy a

Dòng 3: n số miêu tả dãy b

Dòng 4: n số miêu tả dãy c

Dòng 5: n số miêu tả dãy d

Output

Một dòng duy nhất ghi số nguyên kết quả

Example 

Input:

5

4 3 2 1 5

3 4 5 1 2

1 4 3 2 5

1 5 2 3 4
Output:
2
Giải thích: 
Có 2 cặp số thỏa mãn là (2;5) và (4;3)

  • Người up: c_hunter