Computing Sequence Q

Consider the following two sequences (P) and (Q). Sequence (P) is a sorted sequence where for all (k \in \mathbb{Z}^+), the integer (k) appears exactly ((k+1)) times. That is, (P = {1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, \dots}). The sequence (Q) is defined by the recurrence:

[ Q(1) = 1, \quad Q(i) = Q(i-1) + Q(P(i)) \text{ for } i > 1. ]

Given a positive integer (n), compute (Q(n)).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^5\)).

outputFormat

Output the value of \(Q(n)\).

sample

1

1