Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3520
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.


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.


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

Sample Input


Sample Output


Author: JIANG, Kai
Submit    Status