Byteland 是一个美丽的国家，拥有 $n$ ($n \ge 3$) 座城市，这些城市在二维平面上表示为 $n$ 个不同的点。城市编号从 $1$ 到 $n$。作为一名游客，你并不知道这些城市在 Byteland 的确切位置。从一本旅游杂志上你了解到，任意三座城市都不共线。

一组 $n$ 个点的凸包是一个面积最小的凸多边形，使得所有 $n$ 个点都在该多边形的内部或边界上。凸多边形的所有内角都小于 $180$ 度，且不能有自交。

你的任务是求出 Byteland 城市集合的凸包边界上的顶点数量。你只能询问三个不同城市编号 $i, j, k$ ($1 \le i, j, k \le n$) 构成的三元组。此类询问涉及以城市 $i, j, k$ 为顶点的三角形。询问的回答指示按 $i, j, k$ 的顺序遍历三角形顶点是顺时针还是逆时针。

交互

你的程序应使用一个库，该库允许进行询问并提交最终答案。

对于 C 和 C++，库（trilib.h）提供以下函数：

• int get_n(); 返回城市数量。
• bool is_clockwise(int a, int b, int c); 如果三角形 $a, b, c$ ($1 \le a, b, c \le n, a \neq b \neq c \neq a$) 的顶点按顺时针顺序排列，则返回 true；如果按逆时针顺序排列，则返回 false。
• void give_answer(int s);

对于 Java，trilib 类提供以下方法：

• static public int get_n();
• static public boolean is_clockwise(int a, int b, int c);
• static public void give_answer(int s);

在你的程序调用 give_answer 后，不允许再进行任何询问。程序必须且仅能调用 give_answer 一次。

在本题中，不允许从标准输入读取数据或向标准输出写入数据。在调用 give_answer 后，程序应立即终止。

你可以假设点的位置是预先确定的，并且在程序执行期间不会改变（即库的行为是完全确定性的）。例如，在示例测试用例（见下文）中，调用 give_answer(4) 并立即退出即可通过测试。你的程序可以尝试在不确定的情况下猜测答案。

样例

考虑 $n = 6$ 座城市，位置分别为 $(1, 1), (4, 3), (2, 2), (1, 4), (5, 1), (3, 2)$，如下图所示。凸包用线条标记。它在边界上包含四个顶点，因此结果为 $4$。

下表显示了与该示例对应的库交互示例：

下图显示了第一次查询中的三角形。城市 $1, 4, 2$ 按顺时针顺序排列，因此返回值为 true。

子任务

测试集分为以下具有附加约束的子任务。每个子任务中的测试由一个或多个独立的测试组组成。每个测试组可能包含一个或多个测试用例。

在所有测试中，$3 \le n \le 40\,000$。你最多可以调用 is_clockwise $1\,000\,000$ 次。

实现细节

在 public 目录下有一个示例库，允许你测试解决方案的正式正确性。该库从标准输入读取 Byteland 的描述，格式如下：

• 第一行包含一个整数 $n$，即城市数量。
• 接下来的 $n$ 行：每行两个整数，表示第 $i$ 个城市的坐标。

提供的库不会对你的解决方案进行所有检查。它也不检查输入的正确性。它与服务器上的（秘密）库不同。

库的示例输入在 tri0.in 文件中给出。

在调用 give_answer 后，库会将给出的答案和 is_clockwise 的调用次数打印到标准输出。

编译带有示例库的解决方案，可以使用以下命令：

• C: gcc -O2 -static trilib.c tri.c -lm -std=gnu99
• C++: g++ -O2 -static trilib.c tri.cpp -lm -std=c++11

对于 Java，你不需要使用任何特殊命令来编译带有库的解决方案。

解决方案文件和库文件应位于同一目录下。