K. 多少"abc"

题目描述

序列的子序列指从序列中将若干元素（含 $0$ 个）提取出来且并 不改变剩余元素相对位置 形成的序列，例如 '', 'a', 'ab', 'acb' 均为 ''acb'' 的子序列，而 'ca', 'bc' 不是。注意，位置不同但字母相同的子序列在本题中视为不同的子序列，例如， ''aa'' 的子序列共有 '', 'a', 'a', 'aa' 四个。

你的任务是找出在一个长度为 $n$ 的字符串中子序列可能为 "abc" 的最大个数。

输入格式

输入一行一个正整数 $n$ ，代表字符串的长度。

输出格式

输出一个整数，含义见上文。

样例输入

4

样例输出

2

样例解释

对于样例，"aabc", "abbc", "abcc" 均为合法解，子序列 "abc" 的出现次数均为 2。

以 "aabc" 为例，两个子序列分别为 $\underline{\text{a}}\text{a}\underline{\text{bc}}, \text{a}\underline{\text{abc}}$ 。

数据范围及约定

$1 \le n \le 500$