Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
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.

#### 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.

```3
4
```

#### Sample Output

```2
4
```

Author: JIANG, Kai
Submit    Status