Problem:
 Score : 500 points    Problem Statement An adult game master and N children are playing a game on an ice rink.
The game consists of K rounds.
In the i -th round, the game master announces:   Form groups consisting of A_i children each!   Then the children who are still in the game form as many groups of A_i children as possible.
One child may belong to at most one group.
Those who are left without a group leave the game. The others proceed to the next round.
Note that it's possible that nobody leaves the game in some round.  In the end, after the K -th round, there are exactly two children left, and they are declared the winners.  You have heard the values of A_1 , A_2 , ..., A_K . You don't know N , but you want to estimate it.  Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of N exist.      Constraints  1 \leq K \leq 10^5  2 \leq A_i \leq 10^9  All input values are integers.         Input Input is given from Standard Input in the following format:  K  A_1  A_2  ...  A_K       Output Print two integers representing the smallest and the largest possible value of N , respectively,
or a single integer -1 if the described situation is impossible.        Sample Input 1 4
3 4 3 2      Sample Output 1 6 8  For example, if the game starts with 6 children, then it proceeds as follows:   In the first round, 6 children form 2 groups of 3 children, and nobody leaves the game.  In the second round, 6 children form 1 group of 4 children, and 2 children leave the game.  In the third round, 4 children form 1 group of 3 children, and 1 child leaves the game.  In the fourth round, 3 children form 1 group of 2 children, and 1 child leaves the game.   The last 2 children are declared the winners.       Sample Input 2 5
3 4 100 3 2      Sample Output 2 -1  This situation is impossible.
In particular, if the game starts with less than 100 children, everyone leaves after the third round.       Sample Input 3 10
2 2 2 2 2 2 2 2 2 2      Sample Output 3 2 3

Solution (Python):



k = int(input())
a = list(map(int, input().split()))
a= a[::-1]
if a[0]!=2:
    print(-1)
    exit()
mi = a[0]
mx = a[0]*2-1
for i in range(1,k):
    ai = a[i]
    mi = (mi+ai-1)//ai
    mx = mx//ai
    if mi>mx:
        print(-1)
        exit()
    else:
        mi = mi*ai
        mx = (mx+1)*ai-1
print(mi, mx)

Solution (Python):
k = int(input())
a = list(map(int,input().split()))
ansmax = 2
ansmin = 2

for i in reversed(range(k)):
    if ansmax - ansmin < a[i] and (ansmin%a[i])*(ansmax%a[i]) != 0 and (ansmax%a[i]) >= (ansmin%a[i]):
        print(-1)
        exit()
    ansmin = -(-ansmin//a[i])*a[i]
    ansmax = (ansmax//a[i])*a[i] + a[i] - 1
print(str(ansmin) + " " + str(ansmax))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    A = list(map(int, input().split()))[::-1]

    if A[0] != 2:
        print(-1)
    else:
        prev_min, prev_max = 2, 3
        for i in range(1, k):
            a = A[i]
            if a > prev_max:
                print(-1)
                break
            else:
                if prev_min % a == 0:
                    now_min = prev_min
                else:
                    now_min = (prev_min // a + 1) * a
                if now_min > prev_max:
                    print(-1)
                    break
                diff = prev_max - now_min
                now_max = now_min + (diff // a + 1) * a - 1
                prev_min, prev_max = now_min, now_max
        else:
            print(prev_min, prev_max)


if __name__ == '__main__':
    resolve()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.reverse() 

if A[0] != 2:
  print(-1)
  exit()
MIN = 2
MAX = 3
for i in range(1,N):
  nxt = A[i]
  if MAX < nxt:
    print(-1)
    exit() 
  
  MAX = (MAX//nxt)*nxt 
  if MAX < MIN:
    print(-1)
    exit()
  
  MIN = min(MAX,((MIN+nxt-1)//nxt)*nxt)

  
 
  
  MAX = MAX+(nxt-1)
  
print(MIN,MAX)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




K = I()
A = IL()

def is_ok(l,r,a):
  if r-l+1 >= a:
    return True
  else:
    if l%a == 0 or r%a == 0 or l%a > r%a:
      return True
    else:
      return False
now = (2,2)
for a in A[::-1]:
  l,r = now
  if is_ok(l,r,a):
    l = ((l-1)//a)*a+a
    r = (r//a)*a+a-1
    now = (l,r)
  else:
    print(-1)
    exit()
print(*now)

Solution (Python):
K = int(input())
As = list(map(int, input().split()))

def f(n):
    for a in As:
        n = a * (n//a)
    return n

ng,ok = 1, 10**20
while ok-ng > 1:
    m = (ok+ng)//2
    if f(m) >= 2: 
        ok = m
    else:
        ng = m
mn = ok


ok,ng = 1, 10**20
while ng-ok > 1:
    m = (ok+ng)//2
    if f(m) <= 2: 
        ok = m
    else:
        ng = m
mx = ok


if mn > mx:
    print(-1)
else:
    print(mn,mx)

Solution (Python):
K = int(input())
As = list(map(int, input().split()))

def f(n):
    for a in As:
        n = a * (n//a)
    return n

ng,ok = 1, 10**20
while ok-ng > 1:
    m = (ok+ng)//2
    if f(m) >= 2: 
        ok = m
    else:
        ng = m
mn = ok


ok,ng = 1, 10**20
while ng-ok > 1:
    m = (ok+ng)//2
    if f(m) <= 2: 
        ok = m
    else:
        ng = m
mx = ok


if mn > mx:
    print(-1)
else:
    print(mn,mx)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


k = int(input())
a = list(map(int, input().split()))
v1 = 2
v2 = 2
ans = None
for num in a[::-1]:

    
    if (v1-1)//num == (v2)//num:
        ans = -1
        break
    v1 = ((v1-1)//num+1) * num
    v2 = (v2)//num * num + (num-1)
if ans == -1:
    print(ans)
else:
    print(v1,v2)

Solution (Python):
k=int(input())
a=list(map(int,input().split()))
if a[-1]!=2:
  print(-1)
  exit()
l,r=2,2
for i in range(k):
  ai=a[-1-i]
  
  if r<ai or (l//ai==r//ai and l%ai!=0):
    print(-1)
    exit()
  l=ai*((l+ai-1)//ai)
  r=ai*(r//ai)+(ai-1)
print(l,r)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def nn(v, min_v, max_v):
	min_n = (min_v + v - 1) // v
	max_n = max_v // v
	
	if max_n < min_n:
		return -1, -1
	return v * min_n, v * max_n + v - 1

def main():
	n = int(input())
	
	
	al = lin()
	al = al[::-1]
	min_v, max_v = 2, 2
	for v in al:
		min_v, max_v = nn(v, min_v, max_v)
		if min_v == -1:
			return -1
	print(min_v, max_v)
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():

	n=II()
	A=LI()

	if A[-1]!=2:
		print(-1)
		exit()

	l=2
	r=2

	for i in range(n-2,-1,-1):
		l=((l-1)//A[i]+1)*A[i]
		r=((r+A[i+1]-1)//A[i])*A[i]
		if l>r:
			print(-1)
			exit()

	print(l,r+A[0]-1)
















if __name__ == "__main__":
	main()

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():

	n=II()
	A=LI()

	if A[-1]!=2:
		print(-1)
		exit()

	l=2
	r=2

	for i in range(n-2,-1,-1):
		l=((l-1)//A[i]+1)*A[i]
		r=((r+A[i+1]-1)//A[i])*A[i]
		if l>r:
			print(-1)
			exit()

	print(l,r+A[0]-1)
















if __name__ == "__main__":
	main()

Solution (Python):
k=int(input())
a=list(map(int,input().split()))
l,r=2,2
for i in a[::-1]:
 l,r=((l-1)//i+1)*i,(r//i+1)*i-1
 if l>r:exit(print(-1))
print(l,r)

Solution (Python):
def resolve():
    
    k = int(input())
    a = list(map(int, input().split()))
    rl = [2, 2]
    ra = a[::-1]

    for i in range(k):
        nxt = []
        nowa = ra[i]
        if (rl[-1] // nowa) - ((rl[0]-1)//nowa) > 0:
            nxt.append((((rl[0]-1)//nowa)+1)*nowa)
            nxt.append((rl[-1]//nowa)*nowa + nowa-1)
        if not nxt:
            print(-1)
            exit()
        rl = nxt

    print("{} {}".format(rl[0], rl[-1]))
resolve()

Solution (Python):
k = int(input())
a = list(map(int,input().split()))

upper,lower = 2,2

for ai in a[::-1]:
    lower = (1+(lower-1)//ai)*ai
    upper = (1 + upper//ai)*ai -1
    if(upper < lower):
        print(-1)
        exit()
    

print(' '.join(map(str,[lower,upper])))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import math

k = readint()
a = readints()

flag = 0
if a[-1]!=2:
    flag = 1

b = 2
c = 2
for i in range(k-1,0,-1):
    b = math.ceil(b/a[i-1]) * a[i-1]
    c = ((c+a[i]-1)//a[i-1]) * a[i-1]
    if c == 0:
        flag = 1
        break
    if b>c:
        flag = 1
        break

c = c+a[0]-1

if flag:
    print(-1)
else:
    print(b,c)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

def f(A):
    low, high = 2, 2
    for x in A[::-1]:
        low += (-low) % x
        high -= (high) % x
        if low > high:
            print(-1)
            return
        low, high = low, high+(x-1)
    print(low, high)

f(A)

Solution (Python):

"""
逆操作を考える。
何人組を作るということは、modにおける最大値と最小値を求め続けるということ。
そのような組が作れないような場合(全員が脱落するような場合)は、-1を出力。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

k = int(readline())
lst1 = list(map(int,readline().split()))
lst1.reverse()
if lst1[0] != 2:
    print(-1)
    exit()


def min_lot(value,unit):
    if value%unit == 0:
        return value//unit
    else:
        return value//unit + 1
mn = 2
mx = 3
for i in range(1,k):
    res = min_lot(mn,lst1[i])

    if not mn <= res*lst1[i] <= mx:
        print(-1)
        exit()

    mn = res*lst1[i]

    lim = (mx//lst1[i] + 1)*lst1[i] - 1
    mx = lim



print(mn,mx)

Solution (Python):
K = int(input())
S = list(map(int, input().split()))

m = [0]*K
M = [0]*K
m[K-1] = 2
M[K-1] = 3
if S[K-1] != 2:
    print(-1)
else:
    for i in range(K-2, -1, -1):
        if m[i+1]%S[i] == 0:
            m[i] = m[i+1]
        else:
            m[i] = m[i+1]+S[i]-(m[i+1]%S[i])
        if M[i+1]%S[i] == 0:
            M[i] = M[i+1]+S[i]-1
        else:
            M[i] = (M[i+1]//S[i])*S[i]+S[i]-1
        if m[0] > M[0]:
            print(-1)
            break
    else:
        print(m[0], M[0])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if a[-1]!=2:exit(print(-1))
l=r=2
for i in a[::-1]:
  if (l-1)//i==r//i:exit(print(-1))
  l=(0--l//i)*i
  r=(r//i)*i+i-1
print(l,r)

Solution (Python):
import sys
import math

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    K = int(input())
    A = list(map(int, input().split()))

    
    m = 2
    M = 2
    for i in range(K - 1, -1, -1):
        n = (m + A[i] - 1) // A[i]
        tmp_m = n * A[i]
        tmp_M = (M // A[i]) * A[i] + A[i] - 1
        if tmp_m > M or tmp_M < m:
            print(-1)
            return
        m = tmp_m
        M = tmp_M

    print(m, M)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    K = int(input())
    A = list(map(int, input().split()))
    min_ch = 2
    max_ch = 3
    if A[-1] != 2:
        print(-1)
        return
    for i in range(K):
        n = K - i - 1
        if max_ch < A[n]:
            print(-1)
            return
        a = math.ceil(min_ch / A[n])
        b = math.floor(max_ch / A[n])
        min_ch = A[n] * a
        if min_ch > max_ch:
            print(-1)
            return
        max_ch = A[n] * (b + 1) - 1
    print(min_ch, max_ch)


if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil
k = int(input())
A = list(map(int,input().split()))[::-1]
if A[0]!=2:
    print(-1)
    exit()
flg = True
ans = [2,3]
for i in range(1, k):
    a = A[i]
    m = a*ceil(ans[0]/a)
    if m>ans[1]:
        flg = False
        break
    else:
        ans = [m,a*(ans[1]//a+1)-1]
if flg:
    print(*ans)
else:
    print(-1)

Solution (Python):
k = int(input())
ai = [int(i) for i in input().split()]

low = 2
high = 2*10**15
ans = []

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    
    tmp = mid
    
    for i in range(k):
        tmp = tmp // ai[i]
        tmp = tmp*ai[i]
    
    
    if tmp > 2:
        high = mid
    else:
        low = mid

tmp = low

for i in range(k):
    tmp = tmp // ai[i]
    tmp = tmp*ai[i]

if tmp != 2:
    print(-1)
    exit()
        
ans.append(low)

low = 2
high = 2*10**15

flag = True

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    if flag == True:
        flag = False
        mid = 2
    
    tmp = mid
    
    for i in range(k):
        tmp = tmp // ai[i]
        tmp = tmp*ai[i]
    
    
    if tmp > 1:
        high = mid
    else:
        low = mid
    
ans.append(high)
tmp = high
for i in range(k):
    tmp = tmp // ai[i]
    tmp = tmp*ai[i]

if tmp != 2:
    print(-1)
    exit()
print(ans[1],ans[0])

Solution (Python):
K = int(input())
A = list(map(int, input().split()))[::-1]
if A[0] != 2:
  print(-1)
  quit()

left = 2; right = 3
for a in A[1:]:
  ra = right - right%a
  if ra < left:
    print(-1)
    quit()
  l1 = ra; r1 = ra + a - 1
  la = left + (a - (left%a))%a
  l2 = la; r2 = la + a - 1
  left = min(l1, l2)
  right = max(r1, r2)

print(left, right)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
low, high = 2, 2

for a in A[::-1]:
    low += (-low) % a
    high -= high % a
    high += (a-1)

if low > high:
    print(-1)
else:
    print(low, high)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

min = 2
max = 2
for i in reversed(a):
    max = max // i * i + i - 1
    min = (min + i - 1) // i * i

if min >= max:
    print("-1")
else:
    print(min, max)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

k = int(input())
a = list( map(int, input().split()))

if a[-1]!=2:
    print(-1)
    exit()

ma = 2

for i in reversed(range(k)):
    ma = ma//a[i]*a[i] + (a[i]-1)

    if a[i] > ma:
        print(-1)
        exit()

mi = 2

for i in reversed(range(k)):

    mi = -(-mi//a[i])*a[i]

if mi > ma:
    print(-1)
    exit()

print(mi,ma)

Solution (Python):
K=int(input())
A=list(map(int,input().split()))
mb=Mb=2
t=1
for i in A[::-1]:
    if Mb//i*i>=mb:
        Ma=(Mb//i+1)*i-1
    else:
        t=0
        break
    if mb%i==0:
        ma=mb
    elif (mb//i+1)*i<=Mb:
        ma=(mb//i+1)*i
    else:
        t=0
        break
    mb=ma
    Mb=Ma
if t:
    print(ma,Ma)
else:
    print(-1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()
A = LIST()
if A[-1] != 2:
	print(-1)
	exit()

ma = 3
mi = 2

for x in A[::-1]:
	if x > ma:
		print(-1)
		exit()
	elif mi <= x <= ma:
		mi = x
		ma = 2*x-1
	else:
		tmp_mi = -(-mi//x)*x
		tmp_ma = ma//x*x
		if tmp_mi > tmp_ma:
			print(-1)
			exit()
		ma = tmp_ma+x-1
		mi = tmp_mi

print(mi, ma)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

if A[-1] > 2:
    print(-1)
    exit()

"""
愚直解
初めの人数を2から増やしていって確認。範囲が分からないので、間に合わないのは分かるが計算量は分からん。

問題的にも最後から最初に戻るのがよさそう。
問題的に、Aiの処理を受けたすぐの人数をCiとする。また、ラウンドiの後にとりうる最大の人数をHIi,最小をLOiとする
考えるうえでややこしいのだが、

HIi-1                 HIi
 Ci-1   ->  {Ai} ->    Ci
LOi-1                 LOi

の形になっていて、
「LOi-1~HIi-1 の範囲の値が、  Aiの処理を受けたときに、HIiやLOiの範囲に収まらなければならない」
であるので、HIi-1,LOi-1 が Ai,HIi,LOiに依存している。
（HIi,LOiがAiで決まるのではないのに気を付けたい）

最後の状態（HIi = LOi = Ci = 2）が決まっているので、後ろから先頭に戻る形で、HIi-1, LOi-1を決めていく。

LOi-1を　Aiに通した後の値が LOi であるのは自明で、「LOi-1はAiの定数倍かつ、LOi以上」であるから
LOi-1 = (Loi // Ai) * Ai
といえる

HIi-1 を Ai に通した後に、HIi以下に収まらなければならないので、
HIi-1 = (HIi // Ai) * Ai + (Ai - 1)
となる。ここちょっと発想しにくい感じある。
(HIi // Ai + 1) * Ai が、Aiを通すと、HIiを上回るので、これより小さい物の中で最も大きいものを選びたいから。


"""


HI = 2
LO = 2
for i in range(N):
    
    if LO // A[N-i-1] > 0:
        if LO % A[N-i-1] > 0:
            nxt_LO = (LO // A[N-i-1] + 1) * A[N-i-1]
        else:
            nxt_LO = LO
    else:
        nxt_LO = A[N-i-1]

    
    
    nxt_HI = (HI // A[N-i-1]) * A[N-i-1] + (A[N-i-1] - 1)

    if HI > nxt_HI or LO > nxt_LO  or nxt_HI < nxt_LO:
        print(-1)
        exit()

    LO = nxt_LO
    HI = nxt_HI

print(LO, HI)

Solution (Python):
def calc(n, N, x):
    m, M = -1, -1
    L, R = 0, 10**13
    while L+1 < R:
        P = (L+R)//2
        if n <= x*P:
            R = P
        else:
            L = P
    if n <= x*R <= N:
        m = x*R
    L, R = 0, 10**13
    while L+1 < R:
        P = (L+R)//2
        if N < x*P:
            R = P
        else:
            L = P
    if n <= x*L <= N:
        M = x*L + (x-1)
    return m, M

def main():
    k = int(input())
    a = list(map(int, input().split()))
    f = True
    m, M = 2, 2
    for i in reversed(range(k)):
        m, M = calc(m, M, a[i])
        if m == -1 or M == -1:
            f = False
            break
    if f:
        print(m, M)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil as c
input()
m=M=2
for b in map(int,input().split()[::-1]):
  m = c(m/b)*b
  M = c((M+1)/b)*b-1
  if m > M:
    print(-1)
    exit()
print(m,M)

Solution (Python):
import math
n = int(input())
a = [int(i) for i in input().split()]
mi = 2
ma = 2
for b in a[::-1]:
  mi = math.ceil(mi/b)*b
  ma = math.ceil((ma+1)/b)*b-1
  if ma < b or mi > ma:
    print(-1)
    exit()
print(mi,ma)

Solution (Python):
k = int(input())
a = list(map(int, input().split()))

def sim(num):
    for g in a:
        num = g * (num//g)
    return num

l=0
r=100+k*max(a)
while r-l>1:
    mid=(l+r)//2

    if sim(mid) > 2:
        r=mid
    else:
        l=mid
ans_max=l

l=0
r=100+k*max(a)
while r-l>1:
    mid=(l+r)//2

    if sim(mid) < 2:
        l=mid
    else:
        r=mid
ans_min=r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min,ans_max)

Solution (Python):
k = int(input())
a = list(map(int, input().split()))
a.reverse()

mn,mx = 2,2
for g in a:
    mn = g * (((mn - 1) // g) + 1)
    mx = g * (mx//g) + g - 1

    if mn > mx:
        print(-1)
        exit()

print(mn,mx)

Solution (Python):
k,*a = map(int,open(0).read().split())
a = a[::-1]
nmax = 2
nmin = 2
for i in range(k):
  if nmax//a[i]-(nmin-1)//a[i]<=0:
    print(-1)
    exit()
  nmin = ((nmin-1)//a[i]+1)*a[i]
  nmax = (nmax//a[i])*a[i]+a[i]-1
print(nmin,nmax)

Solution (Python):
k = int(input())
a = list(map(int, input().split()))

l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n >= 2:
        r = m
    else:
        l = m

ansl = r
l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n <= 2:
        l = m
    else:
        r = m

ansr = l

if ansl <= ansr:
    print(ansl, ansr)
else:
    print(-1)

Solution (Python):
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a // gcd * b

def main():
    K = int(input())
    A = [int(_n) for _n in input().split()]
    maxnum = 2
    minnum = 2
    for i in reversed(range(0,K)):
        mi = (minnum + A[i] - 1)//A[i] * A[i]
        ma = maxnum // A[i] * A[i]
        
        if mi < minnum or mi > maxnum or ma < minnum or ma > maxnum:
            print(-1)
            return
        minnum = mi
        maxnum = ma+A[i]-1
    print(minnum,maxnum)
main()

Solution (Python):



import sys
readline = sys.stdin.readline

K = int(readline())
A = list(map(int,readline().split()))[::-1] 

mincur = 2
maxcur = 2

def get_min_val(c,a): 
  return ((c - 1)//a + 1) * a

def get_max_val(c,a): 
  return (c // a) * a

if A[0] != 2:
  print(-1)
  exit(0)
  
for i in range(len(A)):
  mincur = mincur
  maxcur = maxcur + A[i] - 1
  if i + 1 < len(A):
    mincur = get_min_val(mincur,A[i + 1])
    maxcur = get_max_val(maxcur,A[i + 1])
    if mincur > maxcur:
      print(-1)
      exit(0)
print(mincur,maxcur)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import math

k = ni()
a = na()

r,l = 2,2

for i in a[::-1]:
    if r < i:
        print(-1)
        exit()
    l = math.ceil(l/i)*i
    r = (r//i)*i+i-1
    if l > r:
        print(-1)
        exit()

print(l,r)

Solution (Python):
k = int(input())
A = list(map(int,input().split()))[::-1]

dp = [[0,0] for _ in range(k+1)]
dp[0] = [2,2]

for i in range(k):
    dp[i+1][0] = ((dp[i][0]-1)//A[i] + 1)*A[i]
    dp[i+1][1] = (dp[i][1]//A[i])*A[i] + A[i] -1
    if dp[i+1][0] > dp[i+1][1]:
        print(-1)
        exit(0)
print(' '.join(str(i) for i in dp[k]))

Solution (Python):
MOD = 10 **9 + 7
INF = 10 ** 10

def main():
    K = int(input())
    A = list(map(int,input().split()))
    m = 2
    M = 2
    flag = True
    for i in range(K - 1,-1,-1):
        x = (m + A[i] - 1)//A[i]
        y = M//A[i]
        if x > y:
            flag = False
            break
        M = y*A[i] + A[i] - 1
        m = x*A[i]
    if flag:
        print(m,M)
    else:
        print(-1)         
if __name__ == '__main__':
    main()

Solution (Python):




K = int(input())
A = list(map(int, input().split()))

if A[-1] > 2:
    print(-1)
    exit()



hi = 2
lo = 2

for i in reversed(range(K)):



    new_hi = hi // A[i] * A[i] + (A[i] - 1)

    if lo // A[i] > 0 and lo % A[i] > 0:
        new_lo = (lo // A[i] + 1) * A[i]
    elif lo // A[i] > 0 and lo % A[i] == 0:
        new_lo = lo
    elif lo // A[i] == 0:
        new_lo = A[i]

    if new_hi < hi or new_lo < lo or new_hi < new_lo:
        print(-1)
        exit()


    

    hi = new_hi
    lo = new_lo


print(lo, hi)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A=A[::-1]
dpmax=[0 for i in range(0,N)]
dpmin=[0 for i in range(0,N)]

for i in range(0,N):
    if i==0:
        if A[0]!=2:
            print(-1)
            break
        else:
            dpmax[0]=3
            dpmin[0]=2
    else:
        testmax=dpmax[i-1]-dpmax[i-1]%A[i]
        if dpmin[i-1]%A[i]!=0:
            testmin=dpmin[i-1]-dpmin[i-1]%A[i]+A[i]
        else:
            testmin=dpmin[i-1]
        if testmax>=dpmin[i-1]:
            dpmax[i]=testmax+A[i]-1
        else:
            print(-1)
            break
        if dpmax[i-1]>=testmin:
            dpmin[i]=testmin
        else:
            print(-1)
            break
else:
    print(dpmin[-1],dpmax[-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    k = II()
    a = LI()
    if a[-1] == 2:
        tmp = [2, 3]
        for ai in a[::-1]:
            tmp0, tmp1 = tmp
            if tmp1 // ai > (tmp0 - 1) // ai:
                tmp = [((tmp0 - 1) // ai + 1) * ai, (tmp1 // ai+1) * ai  - 1]
            else:
                print(-1)
                return
        print(*tmp)
    else:
        print(-1)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
x=2
y=2
A=A[::-1]
for i in range(N):
  if y<A[i]:
    print(-1)
    exit()
  else:
    if x<A[i]:
      x=A[i]
    if x%A[i]!=0:
      x+=A[i]-x%A[i]
    if y%A[i]!=0:
      y-=y%A[i]
    y+=A[i]-1
    if x>y:
      print(-1)
      exit()
print(x,y)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
x=2
y=2
A=A[::-1]
for i in range(N):
  nmin=((x+A[i]-1)//A[i])*A[i]
  nmax=y-y%A[i]
  if nmin>nmax:
    print(-1)
    exit()
  x=nmin
  y=nmax+A[i]-1
print(x,y)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    low = 2
    high = 2
    for a in A[::-1]:
        if(high < a):
            print(-1)
            return
        high = a * (high//a)
        low = a * ceil(low,a)
        if(high<low):
            print(-1)
            return
        high += a-1
    print(low,high)
if __name__ == '__main__':
    main()

Solution (Python):



from math import ceil, floor

def main():
  k = int(input())
  la = list(map(int, input().split()))[::-1]
  l = 2
  r = 2
  for a in la:
    if ceil(l/a) > floor(r/a):
      print(-1)
      return
    l = ceil(l/a) * a
    r = floor(r/a) * a + a - 1
  print(l, r)
      

if __name__=='__main__':
  main()