Известно, что Багдад всегда был городом больших возможностей, а потому со всех уголков страны съезжаются туда люди. А более того, все больше и больше народу из северных стран стремятся попасть в Багдад и поселиться здесь. Большинство из них торгуют на базаре, спекулируя различными товарами. Естественно, что коренным багдадцам житья от них нету. И потому ежедневно отряды стражников ходят по улицам, запрашивая документы у наиболее подозрительных. А уж по рынкам пройтись сам Аллах велел.

Центральный базар Багдада располагается на круглой площади, по периметру которой стоят прилавки. За каждым из них стоит один торговец, каждый из которых либо коренной житель Багдада, либо приезжий. У каждого торговца есть по два соседа, которые стоят рядом соответственно по левую и по правую руку. И про них ему доподлинно известно, являются ли коренными жителями. При этом, как ни странно, каждый из торговцев твердит одно: оба его соседи - приезжие.

Общеизвестный факт, что правоверные багдадцы всегда говорят чистую правду, а приезжие, понятное дело, только и делают, что постоянно врут.

Разобраться сейчас, кто врет, а кто говорит правду трудно, но начальнику стражи нужно определить хотя бы число торговцев, которые являются коренными жителями.

Входные данные

В единственной строке задается целое число N (3 <= N <= 109) - общее количество торговцев на базаре.

Выходные данные

В единственную строку выведите два целых числа - минимальное и максимальное количество честных багдадцев, которое может быть среди этих торговцев.