Perform an operation on an array in O(n)
Yes, you can perform this operation in $O(n)$ using a stack $\mathbb{S}$. 

Before presenting the algorithm directly, I would like to give you an illustration using your example. It is not difficult for you to discover the basic idea on your own.

For your example, I give the states of the stack $\mathbb{S}$. Element $P[i]$ and its $S[i]$ are denoted by a pair (P[i], S[i]). The stack reads from left (bottom) to right (top). 

Notice which elements are popped before (when) $P[i]$ is pushed and how (and why) $S[i]$ is computed (described as // comments).

initialization: empty
P[0] = 4: (4,1)
P[1] = 3: (4,1), (3,1)  
P[2] = 6: (6,3)    // 3 = 1 + 1 + 1
P[3] = 1: (6,3), (1,1)
P[4] = 2: (6,3), (2,2)  // 2 = 1 + 1
P[5] = 7: (7,6)   // 6 = 2 + 3 + 1  
P[6] = 9: (9,7)   // 7 = 6 + 1




Here is the basic idea.

Stack $\mathbb{S}$ stores the elements $P[i]$ in array $P$ and its corresponding (already computed) $S[i]$. 

Initialization: $\mathbb{S}=\emptyset; \quad \forall i: S[i]=0.$

For each element $P[i]$ in array $P$ in order:


$\textsf{Pop}$ the elements in stack $\mathbb{S}$, until it encounters a bigger one than $P[i]$. This step simulates the "advance toward" procedure. Meanwhile, compute the sum of the $s$ values of all elements that are popped by $P[i]$. Then, $S[i]$ for $P[i]$ equals $1$ plus this sum.
Then $\textsf{Push}$ $P[i]$ and its corresponding value $S[i]$ (just computed) into $\mathbb{S}$.