Median Modulo

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

You are given a positive integer N. Calculate the lower median of the numbers N \bmod 1, N \bmod 2, N \bmod 3, \dots, N \bmod N.

The lower median of a sequence of k numbers is the number at position \lfloor \frac{k+1}{2} \rfloor when the sequence is sorted. For example, the lower median of the sequence 1,3,5,7 is 3 and the lower median of the sequence 1,1,2,3,5 is 2.

Input Specification

The first and only line of input contains the integer N.

Constraints

Subtask 1 [10%]

1 \le N \le 10^6

Subtask 2 [20%]

1 \le N \le 10^9

Subtask 3 [20%]

1 \le N \le 10^{12}

Subtask 4 [25%]

1 \le N \le 10^{15}

Subtask 5 [25%]

1 \le N \le 10^{18}

Output Specification

Output one number: the lower median in the problem statement.

Sample Input 1

7

Sample Output 1

1

Explanation for Sample Output 1

The sequence 7 \bmod 1, 7 \bmod 2, 7 \bmod 3, 7 \bmod 4, 7 \bmod 5, 7 \bmod 6, 7 \bmod 7 is equal to 0,1,1,3,2,1,0. When sorted, this becomes 0,0,1,1,1,2,3. The lower median is the 4^\text{th} element of this sorted sequence, which is 1.

Sample Input 2

50

Sample Output 2

6

Comments

There are no comments at the moment.