На півдорозі

Дано ціле число $n$. Потрібно знайти медіану списку всіх цілих чисел від $1$ до n - 1, які є взаємно простими з $n$.

Нагадаємо, що два цілі числа $a$ і $b$ є взаємно простими, якщо їхній найбільший спільний дільник дорівнює 1. Медіаною списку $L$ називається \frac {|L|}{2}-й елемент списку $L$, якщо $|L|$ парне, і \frac {|L|+1}{2}-й елемент списку $L$, якщо $|L|$ непарне. Тут вважається, що $L$ відсортований у порядку зростання, $|L|$ позначає довжину $L$, а індекси починаються з $1$.