## Solution:

First of all, Base on $c_i-c_{i-1}\leq c_{i+1}-c_i$ and $p_i-p_{i-1}\geq p_{i+1}-p_i$ we can roughly found that：

- C is to the left of P. Because C is dense on the left and sparse on the right, P is dense on the right and sparse on the left.
- The maximum interval between any two C or any two P is 1. Because if the interval between two Ps is 2, then the two
`?`

s in the middle of`CP??PP`

can only be C, and the interval between them is 1, which is smaller than the 2 in the leftmost C.

But the above conclusion has 4 special cases:

- There is a P on the far left. Like
`PCCPP`

. - There is a C on the far right. Like
`CCPPC`

. - There is a P on the far left and is a C on the far right. Like
`PCCPPC`

. - Several digits on the left are all P, and all the digits on the left are C. Lke
`PPPPCCC`

.

In the first three special cases, the length of the special bit can only be 1. It is not difficult to find that adding one more bit will produce a result that does not meet the conditions like`PPCCPP`

.

Excluding the fourth special case, the ordinary case + 3 special cases can be expressed as: `(P)?(C){1,}(PC)*(P){1,}(C)?`

. That is, the beginning P is optional, and the end C is optional. Then there are at least one C and P on both sides, and the remaining positions are filled with PC.

So we can notice that for the length of C that has been selected, the more `PC`

, the smaller the sum of P.

So we enumerate the length of C according to 4 cases. Then find the maximum length of `PC`

by binary search. Then we find the number of possibilities for the current case and the selected length of C.

In the second special case, the length of C is 3 as an example：`CCC???????C`

There are the following possibilities: `CCC|PCPCPC|P|C`

, `CCC|PCPC|PPP|C`

, `CCC|PC|PPPPP|C`

, `CCC|PPPPPPP|C`

.

Obviously the less the `PC`

the more the `P`

. So we can get the number of `PC`

s by binary search.

## Code:

## Tips for implementation:

It is recommended to extract a function to specifically binary search the number of `PC`

under the conditions given by the external situation

```
private static long solve(int last_c_pos, int last_unknown_pos, long current_sum_P_minus_C) {
int len = last_unknown_pos - last_c_pos - 1;
if (len % 2 == 1) len--;
int left = 0;
int right = len / 2;
while (left < right) {
// binary search
}
// return the number of all possibilities
}
```