Without loss of generality, let us consider the case \(P_1 < P_N\).

First, let us consider whether a given \(P\) satisfies the condition. We can see that the following is necessary and sufficient:

• There exists some \(1 \leq i \leq N-1\) such that \(P_i \leq P_1\) and \(P_{i+1} \geq P_N\).

We can prove it inductively.

Let us count the permutations \(P\) such that there is no such \(i\) that satisfies the condition above.

Let \(P_N=A+k\). We can immediately see that \(k \geq 2\) is necessary. Let us construct \(P\) as follows.

• Start with a sequence \(P=(A,A+k)\).
• Insert the values \(A+1\) through \(A+k-1\) into \(P\). There are \((k-1)!\) ways to do this.
• Insert the values \(1\) through \(A-1\) into \(P\). When inserting the \(i\)-th of them (\(1 \leq i \leq A-1\)), there are \(k-2+i\) candidates for its position.
• Insert the values \(A+k+1\) through \(N\) into \(P\). When inserting the \(i\)-th of them (\(1 \leq i \leq N-(A+k)\)), there are \(k-2+i\) candidates for its position.

Summing them up, we have \((A+k-3)!(N-A-2)!(k-1)/(k-2)!\) ways. Thus, we want to compute the formula \(\sum_{2 \leq k \leq N-A}(A+k-3)!(N-A-2)!(k-1)/(k-2)!\). We can transform it into \((N-A-2)!(A-1)! \sum_{0 \leq k \leq N-A-2} {A+k-1 \choose k}(k+1)\). Additionally, using \({A+k-1 \choose k} k=A {A+k-1 \choose k-1}\), we can reduce the sum to a formula with a constant number of binomial coefficients. Therefore, we can solve the problem in \(O(1)\) time.