Yet Another Contest 4 P5 - Signpost

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 512M

Problem type

Australia consists of a single long road from west to east. There are N stores along this road, with the i-th store having an integer position of p_i.

You have been commissioned to design and install a signpost. First, you will choose a real number K, representing the position of the signpost. Let d_i = |p_i-K| represent the distance from the signpost to the i-th store. The signpost will contain all N stores on it in some order from top to bottom, under the condition that if d_i < d_j, then store i is listed higher up on the signpost than store j. If two stores are equidistant from the signpost, then you can decide which of stores i and j is listed higher up the signpost.

Your first task is to calculate how many distinct signposts you could make. Since this number may be large, you want to find this number modulo 10^9+7.


1 \le N \le 5 \times 10^5

1 \le p_i \le 5 \times 10^5

All p_i are distinct.

Subtask 1 [50%]

1 \le N \le 3000

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains a single integer, N.

The second line contains N space-separated integers, p_1, p_2, \dots, p_N.

Output Specification

On a single line, print the number of possible distinct signposts, modulo 10^9+7.

Sample Input

1 2 3

Sample Output



Consider the case where the signpost is at position K = 2. Then d_1 = 1, d_2 = 0, d_3 = 1. From the top to bottom, the signpost could list stores 2 then 1 then 3, or stores 2 then 3 then 1.

If we consider all possible values of K, including non-integer and negative values, we see that there are 4 distinct signposts which can be made.


There are no comments at the moment.