4. Given $n$ distinct real numbers, the set of all their permutations is $A_{n}$. For $\left(a_{1}, a_{2}, \cdots, a_{n}\right) \in A_{n}$, if there are exactly two distinct integers $i, j \in\{1,2, \cdots, n-1\}$ such that $a_{i}>a_{i+1}, a_{j}>a_{j+1}$ hold, then the permutation is called a "good permutation". Find the number of "good permutations" in $A_{n}$.
For a permutation $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ in $A_{n}$, if it satisfies $a_{i} > a_{i+1}$, then $a_{i}$ and $a_{i+1}$ are said to form an "adjacent inversion". For $\left(a_{1}, a_{2}, \cdots, a_{n}\right) \in A_{n}$, if it has exactly one adjacent inversion, then the permutation is called a "first-order good permutation", and the number of all first-order good permutations in $A_{n}$ is denoted as $f_{1}(n)$; if it has exactly two adjacent inversions, then the permutation is called a "second-order good permutation", and the number of all second-order good permutations in $A_{n}$ is denoted as $f_{2}(n)$.
It is easy to see that $f_{1}(1)=0, f_{1}(2)=1, f_{1}(3)=4 ; f_{2}(1)=f_{2}(2)=0, f_{2}(3)=1$.
For convenience, we denote the set of all permutations of $k$ distinct real numbers as $A_{k}, k=1,2, \cdots, n$. First, we examine the recursive relationship between $f_{1}(k+1)$ and $f_{1}(k)$.
For each first-order good permutation (denoted as $a$) in $A_{k+1}$, consider the permutation (denoted as $b$) formed by the remaining $k$ numbers $a_{1}, a_{2}, \cdots, a_{k}$ in their original order after removing the largest number $a_{k+1}$.
(1) If permutation $b$ is a first-order good permutation in $A_{k}$ with an adjacent inversion $a_{i} > a_{i+1}$, then in permutation $a$, the position of $a_{k+1}$ can only be between $a_{i}$ and $a_{i+1}$ or at the end;
(2) If permutation $b$ is not a first-order good permutation in $A_{k}$, then the number of adjacent inversions in permutation $b$ is not 1. Clearly, the number of adjacent inversions in permutation $b$ cannot be greater than 1 (otherwise, permutation $a$ would not be a first-order good permutation, noting that $a_{k+1}$ is the largest number in $a_{1}, a_{2}, \cdots, a_{k}, a_{k+1}$, so the number of adjacent inversions in permutation $a$ must be no less than the number of adjacent inversions in permutation $b$), thus the number of adjacent inversions in permutation $b$ is 0, meaning permutation $b$ is a natural permutation. Since permutation $a$ is a first-order good permutation, the position of $a_{k+1}$ cannot be at the end, so $a_{k+1}$ has $k$ possible positions.

In summary, $f_{1}(k+1)=2 f_{1}(k)+k \Rightarrow f_{1}(k+1)+(k+1)+1=2 f_{1}(k)+2 k+2$ $=2\left[f_{1}(k)+k+1\right] \Rightarrow\left\{f_{1}(n)+n+1\right\}$ is a geometric sequence with a common ratio of 2, and $f_{1}(1)+1+1=2$, so $f_{1}(n)+n+1=2^{n} \Rightarrow f_{1}(n)=2^{n}-n-1\left(n \in \mathbf{N}^{*}\right)$.
Next, we examine the recursive relationship between $f_{2}(k+1)$ and $f_{2}(k)$.
For each second-order good permutation (denoted as $c$) in $A_{k+1}$, consider the permutation (denoted as $d$) formed by the remaining $k$ numbers $a_{1}, a_{2}, \cdots, a_{k}$ in their original order after removing the largest number $a_{k+1}$.
(1) If permutation $d$ is a second-order good permutation in $A_{k}$ with adjacent inversions $a_{i} > a_{i+1}, a_{j} > a_{j+1}$, then in permutation $c$, the position of $a_{k+1}$ can only be between $a_{i}$ and $a_{i+1}$, or between $a_{j}$ and $a_{j+1}$, or at the end; (2) If permutation $d$ is not a second-order good permutation in $A_{k}$, then it must be a first-order good permutation in $A_{k}$, with an adjacent inversion $a_{i} > a_{i+1}$. Since permutation $c$ is a second-order good permutation, the position of $a_{k+1}$ cannot be between $a_{i}$ and $a_{i+1}$, nor at the end, so $a_{k+1}$ has $k-1$ possible positions.
In summary, $f_{2}(k+1)=3 f_{2}(k)+(k-1) f_{1}(k)=3 f_{2}(k)+(k-1)\left(2^{k}-k-1\right)$,
Assume $f_{2}(k+1)+[a(k+1)+b] \cdot 2^{k+1}+c(k+1)^{2}+d(k+1)+e$
$=3\left[f_{2}(k)+(a k+b) \cdot 2^{k}+c k^{2}+d k+e\right]=3 f_{2}(k)+3(a k+b) \cdot 2^{k}+3\left(c k^{2}+d k+e\right)$, then $3(a k+b)-2[a(k+1)+b]=k-1 \Rightarrow a=1, b=1$;
$3\left(c k^{2}+d k+e\right)-\left[c(k+1)^{2}+d(k+1)+e\right]=-k^{2}+1 \Rightarrow c=d=-\frac{1}{2}, e=0$. Thus, $\left\{f_{2}(n)+(n+1) \cdot 2^{n}-\frac{1}{2} n(n+1)\right\}$ is a geometric sequence with a common ratio of 3, and $f_{2}(1)+2 \cdot 2-1=3$, so $f_{2}(n)+(n+1) \cdot 2^{n}-\frac{1}{2} n(n+1)=3^{n}$ $\Rightarrow f_{2}(n)=3^{n}-(n+1) \cdot 2^{n}+\frac{1}{2} n(n+1)\left(n \in \mathbf{N}^{*}\right)$.
In summary, the number of "good permutations" in $A_{n}$ is $3^{n}-(n+1) \cdot 2^{n}+\frac{1}{2} n(n+1)\left(n \in \mathbf{N}^{*}\right)$.