Moving Dots
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 2000
Tags: binary search, brute force, combinatorics, math, two pointers

We play a game with $$$n$$$ dots on a number line.

The initial coordinate of the $$$i$$$-th dot is $$$x_i$$$. These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed.

Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving.

After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop.

Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $$$n$$$ dots that has at least two dots. As the result can be very large, print the sum modulo $$$10^9+7$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 3000$$$).

The next line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$$$), where $$$x_i$$$ represents the initial coordinate of $$$i$$$-th dot.

Output format:
Print the sum of results modulo $$$10^9+7$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 1024.0 MB

Note:
In the first example, for a subset of size $$$2$$$, two dots move toward each other, so there is $$$1$$$ coordinate where the dots stop.

For a subset of size $$$3$$$, the first dot and third dot move toward the second dot, so there is $$$1$$$ coordinate where the dots stop no matter the direction where the second dot moves.

For $$$[1, 2, 4, 6]$$$, the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is $$$1$$$ coordinate where the dots stop, which is $$$1.5$$$.

Because there are $$$6$$$ subsets of size $$$2$$$, $$$4$$$ subsets of size $$$3$$$ and one subset of size $$$4$$$, the answer is $$$6 \cdot 1 + 4 \cdot 1 + 1 = 11$$$.

In the second example, for a subset of size $$$5$$$ (when there are dots at $$$1$$$, $$$3$$$, $$$5$$$, $$$11$$$, $$$15$$$), dots at $$$1$$$ and $$$11$$$ will move right and dots at $$$3$$$, $$$5$$$, $$$15$$$ will move left. Dots at $$$1$$$, $$$3$$$, $$$5$$$ will eventually meet at $$$2$$$, and dots at $$$11$$$ and $$$15$$$ will meet at $$$13$$$, so there are $$$2$$$ coordinates where the dots stop.

Example input:
4
1 2 4 6

Example output:
11

Example input:
5
1 3 5 11 15

Example output:
30

Editorial:
Let's think about the original problem where we do not think about subsets.
We can easily observe that each dot does not change direction during moving.
Assume that dots gather at coordinate $$$x$$$. Rightmost dot of dots that have smaller coordinate than $$$x$$$ should move right, and leftmost dot which has bigger coordinate than $$$x$$$ should move left. We can observe that the number of adjacent dot where each move toward each other will be the answer.
Now let's solve the problem for subsets. Instead of counting number of adjacent dot that moves toward each other for each subset of dots, we will count the number of subset for each possible $$$1 \leq i < j \leq N$$$ where dot $$$i$$$ moves right and dot $$$j$$$ moves left and there are no dots between $$$i$$$ and $$$j$$$.
Let the coordinate of a dot in a subset be $$$k$$$. We will try to find out which $$$k$$$ can be in a subset where dot $$$i$$$ and dot $$$j$$$ move toward each other.
Since there are no dot between $$$i$$$ and $$$j$$$, dots satisfying $$$x_i < k < x_j$$$ should not be in the subset. Since dot $$$i$$$ should move right, dots that satisfy $$$k<x_i $$$ and $$$x_i-k \leq x_j-x_i$$$ should not be in the subset. As the same way for dot $$$j$$$, dots that satisfy $$$k>x_j$$$ and $$$k-x_j < x_j-x_i$$$ should not be in the subset. Summing these up, dots satisfying $$$2x_i -- x_j \leq k < 2x_j -- x_i$$$ should not be in the subset. By using binary search, we can find the number of dots that cannot be in the subset in $$$O(logN)$$$.
If there are $$$p$$$ dots that can be in the subset, the number of subset where $$$i$$$ and $$$j$$$ moves toward each other will be $$$2^p$$$. Summing all $$$2^p$$$ will give us the answer. Since there are $$$O(N^2)$$$ pairs of $$$(i, j)$$$, we can solve the problem in $$$O(N^2logN)$$$.
Instead of using binary search, we can use the monotonicity of $$$2x_j-x_i$$$ and $$$2x_i-x_j$$$ when $$$j$$$ increases, we can solve the range of dots that cannot be in the subset in $$$O(N^2)$$$ by sweeping. Both $$$O(N^2logN)$$$ and $$$O(N^2)$$$ solutions will be accepted.
There were some dynamic programming solutions from some testers.