T463178 三角形

给定一个长度为 $n$ 的序列 $a$，有 $q$ 次询问，每次询问一段区间 $[l,r]$，判断能否选出三个不同的下标 $(i,j,k)$，满足以 $(a_i,a_j,a_k)$ 为边长，可以构成三角形

输入数据有 $q+2$ 行 第一行两个整数 $n, q$ 接下来一行 $n$ 个正整数，第 $i$ 个数为 $a_i$ 接下来 $q$ 行，每行两个正整数 $l, r$ 保证 $1 \le l \le r \le n$，代表询问区间 $[l, r]$

$q$ 行，每行请判定，若判定成功则输出 `Triangle` 否则输出 `Not triangle`

| 数据点编号 | | $n, q \le$ | 特殊性质 | | ------------ | ---- | ----------------- | --------------- | | $1 \sim 2$ | | $2 \times 10 ^ 5$ | $n = 1$ | | $3 \sim 6$ | | $10$ | 无 | | $7 \sim 10$ | | $2 \times 10 ^ 5$ | $r - l + 1 = 3$ | | $11 \sim 12$ | | $10 ^ 2$ | 无 | | $13 \sim 14$ | | $5 \times 10 ^ 2$ | 无 | | $15 \sim 16$ | | $10 ^ 3$ | 无 | | $17 \sim 20$ | | $2 \times 10 ^ 5$ | 无 |