Count O(max(N,M))

We can count the number of valid subarrays ending in each index `i`

.

Since the array is already sorted and all elements are unique in `[1, N]`

,

we only have to find the largest index `j`

that is smaller that `i`

that are either poisonous or allergic to each other (hope I understand the question correctly),

then, for that index `i`

, we will update `j`

to `max(j, jump[i])`

The answer will be the sum of all valid subarrays that end at each index `i`

.

`Time O(max(N, M))`

`Space O(N)`

```
private static long solve(int N, int[] P, int[] A){ // Java
int[] jump = new int[N+1];
for (int i = 0; i < P.length; i++){
for (int[] a : new int[][]{{A[i], P[i]}, {P[i], A[i]}}){
if (a[0] < a[1] && a[0] > jump[a[1]]){
jump[a[1]] = a[0]; // log the largest index less than it that are incompatible.
}
}
}
long ans = 0;
for (int i = 0, j = 0; i <= N; i++){
j = Math.max(jump[i], j);
ans += i - j;
}
return ans;
}
```