This problem is an exercise of typical trick on “sum of product” and a hard casework.

See also easier problems on sum of product, such as ABC277-G and ARC157-C.

Key strategies in casework include considering symmetry to reduce the number of cases, which helps minimize errors due to oversight.

---

[1] Rephrasing the problem

The typical trick enables us to rephrase the problem as follows:

For all integer tuples \((l_1,r_1,l_2,r_2)\) with \(1\leq l_1 < r_1 \leq N\) and \(1\leq l_2 \leq r_2 \leq N\), count the number of permutations such that \(P_{l_1}>P_{r_1}\) and \(P_{l_2}>P_{r_2}\), and find their sum of the counts.

Now we consider this rephrased problem. Also, let \(q\) be the number of \(-1\) in \(A\).

---

[2] Casework based on the structure of the pair

The pairs \((l,r)\) such that \(1\leq l<r\leq N\) can be classified into the following three patterns:

• Both \(P_l\) and \(P_r\) are already determined. We call such a pair type \(A\).
• Either \(P_l\) or \(P_r\) is already determined. We call such a pair type \(B\).
• Both \(P_l\) and \(P_r\) are undetermined yet. We call such a pair type \(C\).

For \((l_1,r_1,l_2,r_2)\), we do casework based on what type \((l_1,r_1)\) and \((l_2,r_2)\) are in. By symmetry, it is sufficient to consider the following six cases (note that you need to double the count when the types of \((l_1,r_1)\) and \((l_2,r_2)\) are different), some of which are obvious. We consider the easier patterns first.

---

Notations

• A pair \((l,r)\) of type \(A\) is called good if \(P_l > P_r\). Let \(a\) be such good pairs of type \(A\).

• Let \(c\) be the number of pairs of type \(C\).

---

• Type \(A\) and type \(A\)

The sought contribution is \(a^2 \times q!\).

• Type \(A\) and type \(B\).

Count the conforming permutations for all pairs of type \(B\) and find their sum times \(a\).

• Type \(A\) and type \(C\)

Among the \(q!\) possible permutations, \(q!/2\) of them has an inverted of type \(C\), by symmetry.

The sought contribution is \(a\times c \times q!/2 = ac/2\times q!\).

• Type \(C\) and type \(C\)

It depends on the number of distinct integers in \((l_1,r_1,l_2,r_2)\):

a. If there are two distinct integers

\((l_1,r_1) = (l_2,r_2)\), so the sought contribution is \(c\times q! / 2\).

b. If there are three distinct integers

If \(l_1 = l_2\), we can assume \(r_1<r_2\).

The contribution can be simply computed by fixing the position of \(l_1\) and the value there.

If \(l_1\neq l_2\), we can assume \(l_1 < l_2\). There are two patterns to think about: \(l_2=r_1\) and \(r_1 = r_2\).

For the former, the contribution can be simply computed by fixing the position of \(l_2\) and the value there.

For the latter, the contribution can be simply computed by fixing the position of \(r_2\) and the value there.

c. If there are four distinct integers

We assume \(l_1 < l_2\), and double the count lastly. If we let \(x,y,z,w\ (x<y<z<w)\) be these integers, then there are three possibilities: \((l_1,r_1) = (x,y),(x,z),(x,w)\).

By symmetry, \(1/4\) of the permutations satisfies the condition; thus, the sought contribution is \(2\times \binom{q}{4} \times 3 \times q! / 4 = 3/2\binom{q}{4} \times q!\).

• Type \(B\) and type \(C\)

Enumerate the determined value in a type-\(B\) pair. If a type-\(C\) pair contains neither integer of a type-\(B\) pair, then they are independent, so we can just multiply \(1/2\).

Otherwise, they are not independent, so extra caution is needed. The computation of the contribution can be rather simplified by enumerating all undetermined values of the type-\(B\).

• Type \(B\) and type \(B\)

If you exhaustively iterate through the pairs, it would \(O(N^4)\) time. Instead, we consider whether the determined elements in the pairs are the same element.

a. If the two pairs share the same determined element

We need to consider the three kinds of constraints, which can be easily handled by fixing the determined element.

b. If the two pairs have different determined element

Further casework is needed: whether they share the same undetermined element. It is basically same as a., but some cases must be elided to avoid duplicates.

All the six patterns so far run in \(\mathrm{O}(N^2)\) time with careful implementation. Therefore, the problem can be solved in \(\mathrm{O}(N^2)\) time.