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
hide comments
Sushovan Sen:
2021-11-11 12:05:43
Can you please confirm if my solution is giving WA for all files or in some special cases? |
|
packo00111:
2021-05-03 09:55:15
I have some questions:
|
|
champion812r:
2021-04-30 15:17:45
Can you please explain me second output?
|
|
bad_grandpa:
2021-01-12 01:43:23
Plug-In type the is best. I'll be looking forward to finish this. |
|
Vipul Srivastava:
2020-11-14 14:52:28
A1 = A0 + (1-1)*d
|
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 |