Restore Modulo solution codeforces
For the first place at the competition, Alex won many arrays of integers and was assured that these arrays are very expensive. After the award ceremony Alex decided to sell them. There is a rule in arrays pawnshop: you can sell array only if it can be compressed to a generator.
This generator takes four non-negative numbers nn, mm, cc, ss. nn and mm must be positive, ss non-negative and for cc it must be true that 0≤c<m0≤c<m. The array aa of length nn is created according to the following rules:
- a1=smodma1=smodm, here xmodyxmody denotes remainder of the division of xx by yy;
- ai=(ai−1+c)modmai=(ai−1+c)modm for all ii such that 1<i≤n1<i≤n.
Restore Modulo solution codeforces
For example, if n=5n=5, m=7m=7, c=4c=4, and s=10s=10, then a=[3,0,4,1,5]a=[3,0,4,1,5].
Price of such an array is the value of mm in this generator.
Alex has a question: how much money he can get for each of the arrays. Please, help him to understand for every array whether there exist four numbers nn, mm, cc, ss that generate this array. If yes, then maximize mm.Input
The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of arrays.
The first line of array description contains a single integer nn (1≤n≤1051≤n≤105) — the size of this array.
The second line of array description contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109 ) — elements of the array.
It is guaranteed that the sum of array sizes does not exceed 105105.Output Restore Modulo solution codeforces
For every array print:
- −1−1, if there are no such four numbers that generate this array;
- 00, if mm can be arbitrary large;
- the maximum value mm and any appropriate cc (0≤c<m0≤c<m) in other cases.
Exampleinput Restore Modulo solution codeforcesCopy
6 6 1 9 17 6 14 3 3 4 2 2 3 7 3 4 3 2 2 4 5 0 1000000000 0 1000000000 0 2 1 1
outputCopy Restore Modulo solution codeforces
19 8 -1 -1 -1 2000000000 1000000000 0
Answer:
#include<bits/stdc++.h>
#define ll long long int
#define vl vector<ll>
#define pl pair<ll,ll>
#define pb push_back
#define F first
#define S second
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t,n,i,j,k,c,m,s,idxd,idxi,mx=0;
cin >> t;
while(t–)
{
cin >> n;
mx=-1;
vl arr(n,0);
for(i=0;i<n;i++)
{
cin >> arr[i];
mx=max(mx,arr[i]);
}
idxi=-1;
idxd=-1;
for(i=0;i<n-1;i++)
{
if(arr[i]<arr[i+1])
{
idxi=i;
break;
}
}
for(i=0;i<n-1;i++)
{
if(arr[i]>arr[i+1])
{
idxd=i;
break;
}
}
set<ll> st;
for(i=0;i<n-1;i++)
st.insert(arr[i+1]-arr[i]);
if(st.size()==1)
cout << “0\n”;
else if((idxi==-1)||(idxd==-1))
cout << “-1\n”;
else
{
c=arr[idxi+1]-arr[idxi];
m=arr[idxd]+c-arr[idxd+1];
if((c>=m)||(mx>=m))
cout << “-1\n”;
else
cout << m << ” ” << c << “\n”;
}
}
return 0;
}
