Range Collision Survivor Counts

You are given an array values of nonzero integers. Each value moves along a line: the sign is its direction (positive moves right, negative moves left) and the absolute value is its size.

When a right-moving value and a left-moving value meet, they collide: the one with the smaller absolute value is destroyed; if their absolute values are equal, both are destroyed. After a collision, the surviving value (if any) continues and may collide again. Two values moving in the same direction never meet, and a left-moving value that starts to the left of a right-moving value moves away from it, so they never meet either.

You are also given an array queries where queries[j] = [l, r]. For each query, consider only the values values[l..r] (inclusive), in their original order, and let all collisions play out among them alone.

Return an array where entry j is the number of values that survive for query j. Queries are independent; the array is restored between queries.

Examples

Example 1

Input: values = [5,10,-5,8,-8,3], queries = [[0,2],[3,4],[0,5],[2,3]]
Output: [2,0,3,2]
Explanation:
Query [0,2] runs on [5,10,-5]: the -5 collides with 10 and is destroyed, leaving [5,10], so 2 survivors.
Query [3,4] runs on [8,-8]: equal sizes destroy each other, so 0 survivors.
Query [0,5] runs on the whole array: -5 is destroyed by 10, then 8 and -8 destroy each other, then 3 joins, leaving survivors [5,10,3], so 3.
Query [2,3] runs on [-5,8]: -5 moves left and 8 moves right, so they never meet, giving 2 survivors.

Example 2

Input: values = [-2,-1,1,2], queries = [[0,3],[1,2]]
Output: [4,2]
Explanation: The left-movers are already to the left of the right-movers, so no collisions happen in either query.