class FenwickTree {

    private int[] tree;

    public FenwickTree(int size) {
        tree = new int[size + 1];
    }

    public void update(int index, int delta) {
        index++;
        while (index < tree.length) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        index++;
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= index & -index;
        }
        return res;
    }
}

class Solution {

    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] pos2 = new int[n], reversedIndexMapping = new int[n];
        for (int i = 0; i < n; i++) {
            pos2[nums2[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            reversedIndexMapping[pos2[nums1[i]]] = i;
        }
        FenwickTree tree = new FenwickTree(n);
        long res = 0;
        for (int value = 0; value < n; value++) {
            int pos = reversedIndexMapping[value];
            int left = tree.query(pos);
            tree.update(pos, 1);
            int right = (n - 1 - pos) - (value - left);
            res += (long) left * right;
        }
        return res;
    }
}

// Brute Force - TLE
// public long goodTriplets(int[] nums1, int[] nums2) {
//     int n = nums1.length;
//     long ans = 0;
//     Map<Integer, Integer> n2 = new HashMap<>();
//     for (int i = 0; i < n; i++)
//         n2.put(nums2[i], i);
//     for (int i = 1; i < n - 1; i++) {
//         int i2 = n2.get(nums1[i]);
//         int less = 0, more = 0;
//         for (int j = i - 1; j >= 0; j--) {
//             if (n2.get(nums1[j]) < i2)
//                 less++;
//         }
//         for (int j = i + 1; j < n; j++) {
//             if (n2.get(nums1[j]) > i2)
//                 more++;
//         }
//         ans += less * more;
//     }
//     return ans;
// }