主元素问题分治法，输入数据由文件名为input3.txt文件提供。文件的第1行为数组S中元素个数n；接下来的n 行中，每行有一个自然数。程序运行结束时，将计算结果输出到文件output3.txt中。输出文件中包含问题的答案：找不到主元素时给出null，找到时给出主元素的值。

主元素问题是分治算法的一个应用，尤其常见于排序和查找问题中。给定一个非空整数数组 `S`，目标是寻找数组中的“主元素”——即满足以下条件的最小正整数 `k`：对于数组中的每个 `i`，`S[i] - k` 至少出现一次，并且 `k` 本身也至少出现一次。这个问题通常会用到二分查找的思想。

首先，你需要按照以下步骤操作：

1. **读取输入**：从文件 "input3.txt" 中读取数据，第一行是一个整数 `n` 表示数组长度，接下来 `n` 行分别代表数组 `S` 的元素。

with open('input3.txt', 'r') as f:
    n = int(f.readline())
    S = [int(line) for line in f]

2. **处理**：由于问题规模可能较大，可以采用分治策略。可以先尝试在一个较小范围内（如数组的一半）查找是否能找到主元素。如果找不到，再扩大范围搜索。这里可以用二分查找算法，每次将范围缩小一半。

3. **递归过程**：
- 定义一个辅助函数，例如 `find_principal_element(left, right)`，接受左右边界作为参数。
- 如果 `left > right`，说明范围已经缩小到单个元素，直接返回该元素（可能是主元素，也可能是不存在的情况）。
- 否则，取区间的中间点 `mid`，检查 `S[mid]` 是否可能是主元素。
- 检查 `S[mid] - S[i]` 是否在 `S` 中存在，以及 `S[mid]` 自身是否存在。
- 如果两者都存在，那么 `S[mid]` 就是主元素。
- 如果只有一个条件满足，则需要继续在左侧或右侧查找，根据结果更新左边界或右边界。

4. **编写输出**：当找到主元素后，将其写入 "output3.txt" 文件。如果没有找到，则输出 "null"。

5. **关闭文件**：记得在完成所有操作后关闭文件。