Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction $\frac{a}{b}$ is called proper iff its numerator is smaller than its denominator (a < b) and that the fraction is called irreducible if its numerator and its denominator are coprime (they do not have positive common divisors except 1).

During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to n instead of the expected decimal notation. 

Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction $\frac{a}{b}$ such that sum of its numerator and denominator equals n. Help Petya deal with this problem.

 


-----Input-----

In the only line of input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.


-----Output-----

Output two space-separated positive integers a and b, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum.


-----Examples-----
Input
3

Output
1 2

Input
4

Output
1 3

Input
12

Output
5 7

Difficulty: interview

Starter code:

Solutions:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = n//2
    b = n-a
    while fractions.gcd(a,b) > 1:
        a -= 1
        b += 1

    return "{} {}".format(a,b)

print(main())





def list_input():
    return list(map(int,input().split()))
def map_input():
    return map(int,input().split())
def map_string():
    return input().split()

from fractions import gcd
    
n = int(input())    
a = n//2
b = n-a
while gcd(a,b) != 1:
  a -= 1
  b += 1
print(a,b)  

def gcd(a,b):
	return gcd(b,a%b) if a%b else b

n = int(input())
for i in range(n):
	num = n - i
	if(num < i):
		if(gcd(num,i) == 1):
			print(num,i)
			break

from fractions import gcd
m=-1
a=-1
b=1
n=int(input())
for i in range(n//2, -1, -1):
    if gcd(i, n-i)==1 and i!=n-i:
        if (i/(n-i))>m:
            m=(i/(n-i))
            a=i
            b=n-i
print(a,b)


from fractions import gcd

n = int(input())

a,b = n//2, (n+1)//2

while gcd(a,b) != 1:
    a -= 1
    b += 1

print(a,b,sep=' ')


n = int(input())

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

ans = None
for i in range(n):
    if i >= n -i:
        break
    if gcd(i, n-i) == 1:
        ans = [i, n-i]
print(ans[0], ans[1])

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

n = int(input())

a = (n - 1) // 2
while (gcd(a, n - a) != 1): a -= 1
print(a, n - a)

n = int(input())

from fractions import gcd
for a in reversed(range(1,n//2+1)):
  b = n-a
  if gcd(a,b) == 1:
    print(a,b)
    break

n = int(input())

def gcd(a, b):
  if a > b:
    return gcd(b, a)
  elif a == 0:
    return b
  elif a == 1:
    return 1
  else:
    return gcd(b % a, a)


if n % 2 != 0:
  print(n // 2, n - n // 2)
else:
  c = n // 2
  while gcd(c, n - c) > 1:
    c -= 1
  print(c, n - c)

import sys
from fractions import gcd


def main():
    n = int(input())
    a = n // 2
    if n % 2 == 0:
        a -= 1

    b = n - a
    while gcd(a, b) > 1:
        a -= 1
        b += 1
    print(a, b)


main()


def NOD(a,b):
    while a > 0 and b > 0:
        if a > b:
            a = a%b
        else:
            b = b%a
    return a+b
n = int(input())
a = 1
b = n-1
maximal = []
while b > a:
    if NOD(a,b) == 1:
        maximal = [a,b]
    b = b-1
    a = a+1
print(maximal[0],maximal[1])



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

n = int(input())
a, b = n // 2, n // 2 + n % 2
while gcd(a, b) > 1:
    a -= 1
    b += 1
print(a, b)

from fractions import gcd, Fraction

n = int(input())
p = Fraction(0)

for i in range(n + 1):
	if n - i <= i:
		break
	if gcd(i, n - i) == 1:
		p = max(p, Fraction(i, n - i))

a, b = str(p).split('/')
print(a, b)


n = int(input())

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

max = 1
for i in range(1, n//2 + 1):
	if gcd(i, n-i) == 1:
		max = i

print(max, n-max)

def g(a,b):
	if(b>a):
		return g(b,a)
	if(b== 0 ):
		return a
	return g(b,a%b)

n = int(input())
if(n%2 == 1):
	a = n//2
	b = n-n//2
else:
	a = n-n//2 - 1
	b = n-n//2 + 1
while(g(b,a) > 1):
	a -= 1
	b += 1
print(a,b)

from math import gcd

n = int(input())
curr_opt_a = 1
for a in range(n - 1, 0, -1):
    b = n - a
    if a >= b:
        continue
    if gcd(a, b) == 1:
        curr_opt_a = max(curr_opt_a, a)
print(curr_opt_a, n - curr_opt_a)

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

n = int(input())
for i in range(1, n):
    if i > n - i and gcd(i, n - i) == 1:
        print(n - i, i)
        break


def gcd(a, b):
    while a>0 and b > 0:
        if a > b:
            a %= b
        else:
            b %= a
    return a + b

n = int(input())
for i in range(n // 2, 0, -1):
    if gcd(i, n - i) == 1:
        print(i, n - i)
        break

from sys import stdin, stdout
import math

n = int(stdin.readline().rstrip())

if n%2==0:
    n1=n//2
else:
    n1 = n//2

foundGCD = False
for i in range(n1,1,-1):
    n2 = n-i
    if math.gcd(i,n2)==1:
        foundGCD = True
        print(str(i) + ' ' + str(n2))
        break

if not foundGCD:
    print(str(1) + ' ' + str(n-1))


def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)
  
def main():
  n = int(input())
  res = (0, 1)
  
  for i in range(1, n):
    a, b = i, n - i
    if b <= a:
      break
    g = gcd(a, b)
    if g != 1:
      continue
    if a * res[1] > b * res[0]:
      res = (a, b)

  print(res[0], res[1])
  
main()

#! /usr/bin/env python3

import math

n = int(input())

for num in range(1,n):
    if 2* num > n and math.gcd(n - num, num) == 1:
        print(n - num, num)
        break


def nod(a,b):
    if b == 0:
        return a
    else:
        return nod(b, a % b)
n = int(input())
m = 0
a = 0
b = 0
for i in range(1, n // 2 + 1):
    if nod(n - i, i) == 1:
        m = max(m,nod(n-i, i))
        a, b = i, n - i
print(a, b)
        


from math import gcd 
n = int(input())

fracs = []
for a in range(1, n):
	b = n - a
	if gcd(a, b) == 1 and a < b:
		fracs.append([a, b])

max_a = None
max_b = None
max_frac = -1

for frac in fracs:
	value = frac[0]/frac[1] 
	if value > max_frac:
		max_frac = value
		max_a = frac[0]
		max_b = frac[1]

print(max_a, max_b) 


import sys
input = sys.stdin.readline

from fractions import gcd


def main():
    a=int(input())
    b=[]
    for i in range(1,a+1):
        if(gcd(i,a-i)==1 and i<a-i):
            b.append([i/(a-i),[i,a-i]])
    
    b.sort()
    print(b[-1][1][0],b[-1][1][1])
    
main()

from sys import stdout
from random import randint 
from math import *
import re


n = int(input())
mx = 0
mx = mxb = 0
for a in range(1, (n + 1) // 2):
    b = n - a
    t = gcd(a, b)
    if t == 1 and mx < a / b:
        mx = a / b
        mxa = a
        mxb = b

print(mxa, mxb)