Hello, Gensokyo

Time Limit: 2 Seconds
Memory Limit: 65536 KB

*Shameimaru Aya* is a *tengu* who has been in for over 1000 years. As a famous journalist, she writes up her non-periodical newspaper, *Bunbunmaru News*, which is a newspaper chock-full of rumors. Especially, she loves gossip and is always gathering information about the secret relationships between girls in *Gensokyo*.

After a long time investigation, she found some interesting facts. In *Gensokyo*, there are `N` girls. Some pair of girls loves each other. Here is an example of some pairs of relationships: *Patchouli* <-> *Marisa*, *Alice* <-> *Marisa*, *Marisa* <-> *Reimu* (it is a kind of bidirectional relationship). According to the discovery of *Shameimaru Aya*, any 3 out of the `N` girls won't love each other. In another word, there are at most 2 secret relationships among any 3 girls.

Because *Shameimaru Aya* is the biggest connoisseur of rumors about the girls of *Gensokyo*, she wants to know the maximal possible number of secret relationships between girls.

#### Input

There are multiple test cases. For each test case:

There is only one line contains an integer `N` (1 <= `N` <= 100000) indicates the number of girls in *Gensokyo*.

#### Output

For each test case, output the maximal possible number of secret relationships between girls.

#### Sample Input

3
4

#### Sample Output

2
4

Author:

**JIANG, Kai**
Submit
Status