Gym - 101733D Triangle Construction

Little Andrey wants to work in IT. He already knows that he should exercise in mathematics and algorithms.
Andrey likes to play with a set of wooden sticks of various lengths. Experimentally he found that three sticks can form a triangle, if the length of the longest of them is strictly less than the sum of two others.
A sequence of n sticks is located on the table. Andrey chooses some interval with indices from l to r and looks for three sticks which can form a triangle.
Help Andrew, for each of the q intervals find three sticks such that he can make a triangle.
Input The first input line contains two integers n and q (1 ≤ n, q ≤ 300 000), number of sticks and number of intervals. The second line contains n integers li (1 ≤ li ≤ 1018), the array of sticks length in the order they lie on the table.
Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n), the interval boundaries.
Output For each interval print any three different indices i j k (l ≤ i, j, k ≤ r) such that sticks with lengths li lj lk make a triangle. If there are no such indices, output the only number  - 1.
Example Input 5 3 1 3 1 3 1 1 3 2 4 1 5 Output -1 2 3 4 1 3 5
三角形を構成する3つのエッジがあるかどうかを尋ねる数値といくつかのクエリーを与えます.定理の両側の和が最長より大きい辺に基づいて三角形を構築することができ、まず切り取り部分を並べ替え(テーマはインデックスの出力を要求するため、ここではデータ構造を打ってインデックスを記録する)、それから順番に前の2つの辺を加えて、第3の辺より大きいかどうかを比較する.
test 5クレイジータイムアウト......、チームメイトはtest 5が最悪の可能性が高いと考えている(ソート後はフィボナッチ数列になる).最悪の場合、無解かもしれません.しかし、フィボナッチ数列は増加し続け、88位になるとテーマのデータの上限を超えているため、フィボナッチ数列は最大88個続く!88個以降は解のある他の数列しかありません.そのため、最適化のために巧みに使用することができます.

if (b - a > 88) {
    b = a + 88;
}

88個を超えて直接89にジャンプする......非常に的確な「最適化」と言える.そしてtest 5はやはり低空を飛んでいきました・・・
acコード:

public class Main {
    public static void main(String[] args) {
        //   reader     bufferedReader  ，    
        PrintWriter out = new PrintWriter(System.out);
        int n = reader.nextInt();
        int q = reader.nextInt();
        if (n < 3) {
            while (q-- > 0) {
                System.out.println(-1);
            }
            return;
        }
        long[] list = new long[n + 5];
        for (int i = 1; i <= n; i++) {
            list[i] = reader.nextLong();
        }
        while (q-- > 0) {
            int a = reader.nextInt();
            int b = reader.nextInt();
            if (b - a > 88) {
                b = a + 88;
            }
            ArrayList check = new ArrayList();
            for (int i = a; i <= b; i++) {
                check.add(new Pair(list[i], i));
            }
            Collections.sort(check);
            boolean canMake = false;
            for (int i = 2, len = check.size(); i < len; i++) {
                canMake = check.get(i - 2).first + check.get(i - 1).first > check.get(i).first;
                if (canMake) {
                    out.println(check.get(i - 2).second + " " + check.get(i - 1).second + " " + check.get(i).second);
                    break;
                }
            }
            if (!canMake) {
                out.println(-1);
            }
        }
        out.close();
    }
}

class Pair implements Comparable {
    long first;
    long second;

    public Pair(long first, long second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        if (this.first > o.first) {
            return 1;
        } else if (this.first < o.first) {
            return -1;
        }
        return 0;
    }
}