CF1248D1 The World Is Just a Programming Task (Easy Version)

这是该问题的简化版。在本版本中，$n \le 500$。 Vasya 是一位经验丰富的编程竞赛题目开发者。和所有伟大的人一样，Vasya 也曾遇到过创作瓶颈。为了解决这个问题，Petya 送给了他一个只包含左括号和右括号的字符串。Petya 认为，一个括号字符串的美丽值是其所有循环移位中，能够构成合法括号序列的个数。 为了转移注意力，Vasya 决定从字符串中任选两个位置（可以相同），并交换这两个位置上的字符。Vasya 只会执行一次这样的操作。他想知道，通过这样的操作，字符串的最大美丽值是多少。请你帮助他。 我们提醒你，括号序列 $s$ 被称为合法的，当且仅当： - $s$ 为空； - $s$ 形如“($t$)”，其中 $t$ 是合法括号序列； - $s$ 形如 $t_1 t_2$，即 $t_1$ 和 $t_2$ 的连接，其中 $t_1$ 和 $t_2$ 都是合法括号序列。 例如，“(()())”、“()” 是合法的，而 “)(” 和 “())” 不是合法的。 长度为 $n$ 的字符串 $s$ 的循环移位 $k$（$0 \leq k < n$）是指将字符串 $s$ 的最后 $k$ 个字符与前 $n-k$ 个字符连接起来。例如，字符串 “(())()” 的循环移位 $2$ 是 “()(())”。 如果 $i \ne j$，则循环移位 $i$ 和 $j$ 被认为是不同的。

第一行包含一个整数 $n$（$1 \le n \le 500$），表示字符串的长度。 第二行包含一个恰好由 $n$ 个字符组成的字符串，每个字符都是 “(” 或 “)”。

第一行输出一个整数，表示通过交换任意两个字符后，字符串能够达到的最大美丽值。 第二行输出两个整数 $l$ 和 $r$（$1 \leq l, r \leq n$），表示应交换的两个字符的位置。 如果有多种交换方式可以达到最大美丽值，输出任意一种即可。

在第一个样例中，我们可以交换第 $7$ 个和第 $8$ 个字符，得到字符串 “()()()()()”。该字符串的循环移位 $0, 2, 4, 6, 8$ 都是合法括号序列。 在第二个样例中，交换第 $5$ 个和第 $10$ 个字符后，得到字符串 “)(())()()(()”。其循环移位 $11, 7, 5, 3$ 都是合法括号序列。 在第三个样例中，任意交换两个括号，合法括号序列的循环移位数都是 $0$。 由 ChatGPT 4.1 翻译