DIFFICULTY:
2169
Consider a binary string S of length N+1, where S_i = 1 if P_i<P_{i+1} and S_i = 0 otherwise. Clearly, we have A_ i = 3 \iff S_i = S_{i+1} = 0, A_i = 0 \iff S_i = S_{i+1} = 1. If S_i \neq S_{i+1}, then A_i can be both 1 and 2.
So, we get some conditions of form S_i = S_{i+1} = 0, S_i = S_{i+1} = 1, S_i \neq S_{i+1}. I claim that if there exists a binary string satisfying all these conditions then there exists a corresponding permutation. Indeed, let’s build a permutation of length N+1 for the A_1, A_2, \ldots, A_{N-1}. Then:
- If A_N = 0, just set P_{N+2} = N+2.
- If A_N = 3, set P_{N+2} = 1, and increase all previous elements by 1.
- If A_N = 1, and P_N = x, then set P_{N+2} \to x+1, P_N \to x, and increase all other elements which are at least x+1 by 1.
- If A_N = 2, and P_N = x, then set P_{N+2} \to x, P_N \to x+1, and increase all other elements which are at least x+1 by 1.
Now, how to check if such a string S exists? Start with S_1 = 0 or 1, build string based on conditions S_i = or \neq S_{i+1}, check if it satisfies all the conditions.