/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
Scanner sc
= new Scanner
(System.
in); int n=sc.nextInt();
Queue<Integer> q= new LinkedList<Integer>();
Queue<Integer> q1= new LinkedList<Integer>();
q.offer(0);
for(int i=1;i<=n;i++)
{
int j=i;
while(!q.isEmpty())
{
int x=q.poll();
int res1=x-i;
int res2=x+i;
q1.offer(res1);
q1.offer(res2);
if(q1.contains(n))
{
return;
}
}
q.addAll(q1);
q1= new LinkedList<Integer>();
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVNjYW5uZXIgc2MgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCWludCBuPXNjLm5leHRJbnQoKTsKCQlRdWV1ZTxJbnRlZ2VyPiBxPSBuZXcgTGlua2VkTGlzdDxJbnRlZ2VyPigpOwoJCVF1ZXVlPEludGVnZXI+IHExPSBuZXcgTGlua2VkTGlzdDxJbnRlZ2VyPigpOwoJCXEub2ZmZXIoMCk7CgkJZm9yKGludCBpPTE7aTw9bjtpKyspCgkJewoJCQlpbnQgaj1pOwoJCQl3aGlsZSghcS5pc0VtcHR5KCkpCgkJCXsKCQkJaW50IHg9cS5wb2xsKCk7CgkJCWludCByZXMxPXgtaTsKCQkJaW50IHJlczI9eCtpOwoJCQlxMS5vZmZlcihyZXMxKTsKCQkJcTEub2ZmZXIocmVzMik7CgkJCQoJCQlpZihxMS5jb250YWlucyhuKSkKCQkJewoJCQkJU3lzdGVtLm91dC5wcmludGxuKGkpOwoJCQkJcmV0dXJuOwoJCQl9CgkJCX0KCQkJcS5hZGRBbGwocTEpOwoJCQlxMT0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oKTsKCQl9Cgl9Cn0=