CPDUEL5B - Asacoco Prescription

Watame needs to consume asacoco. However, consuming too much asacoco can be dangerous, so she consults with a doctor.

The doctor recommends her a limit for every day. Let Ai be a real number denoting the limit of asacoco allowed to be consumed in the i-th day.

Uniquely, the array Ai is a non-decreasing arithmetic sequence.

An element Ai can be represented as A0 + i * d where d is a constant real number. It is guaranteed that A0 is an integer.

After receiving the doctor's prescription, Watame went home only to realise the receipt has a different array from the recommendation given from the doctor. 

What was printed on the receipt was an array of integers Si with a note that Si = [Ai].

Here, [x] denotes the largest integer less than or equal to x (floor function).

For rehabilitation, Watame is forced to minimize d (since minimizing d minimizes Ai too, thus less asacoco for Watame) such that the information printed on the receipt is still valid.

If there exists a valid d, it can be represented as a fraction P / Q where GCD(P, Q) = 1. Print the answer in the form of P * Q-1 modulo 109 + 7.

There can be cases where the receipt can be faulty (the cashier and the doctor may as well be drunk of asacoco) and there is no valid d. In this case, print -1 instead.

Input

The first line contains an integer N, the size of the array S.

The next lines contains N integers Si.

Output

Print an integer representing the answer in the form of P * Q-1 modulo 109 + 7.

If there does not exist a valid d (the receipt may be faulty), print -1 instead.

Example

Input 1:
6
1 2 3 4 5 6

Output 1:
1
Input 2:
5
3 3 3 3 4

Output 2:
250000002
Input 3:
2
4 1

Output 3:
-1

Explanation

The answers for sample 1 and 2 in decimal format is 1.0 and 0.25 respectively.

Constraints

1 ≤ N ≤ 105

1 ≤ Si ≤ 109


Added by:Maximilliano
Date:2020-11-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem

hide comments
2021-11-11 12:05:43 Sushovan Sen
Can you please confirm if my solution is giving WA for all files or in some special cases?
2021-05-03 09:55:15
I have some questions:
1Q - Is d=0 valid d ? If it is, we don't have limit for Q.
2Q What is order of given array ? S0, S1,..,Sn-1 or something else ?

[Author]
1. d can be 0, but then P = 0 and Q is any number that is not 0, hence P * Q^-1 = 0 nonetheless the value of Q
2. Yes, the input is given in S0, S1, .., Sn-1


Last edit: 2021-10-08 04:15:33
2021-04-30 15:17:45
Can you please explain me second output?

[Author]
Try d = 0.25, we have A = {3, 3.25, 3.5, 3.75, 4}. This array is valid. If we use a smaller d such as 0.2, we wont get floor(A4) = 4

Last edit: 2021-10-08 04:16:38
2021-01-12 01:43:23
Plug-In type the is best. I'll be looking forward to finish this.
2020-11-14 14:52:28 Vipul Srivastava
A1 = A0 + (1-1)*d
A1 = A0
So by this definition the answer of Test Case 1 should be -1.
Am I missing something?

[Author]: oh sorry, missed that, fixed, thank you

can you take a quick look at my last submission and let me know if I am missing a lot of tests?

[Author]: You're solution may be correct if the problem asks for decimals. But the problem asks for the exact form of X/Y and your solution will give precision errors.

Last edit: 2020-11-23 08:49:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.