23744번 - 알고리즘 과외

지환이(롸롸롸롸)가 운영하는 알고리즘 학원에는 $N$명의 학생이 있고, 각 학생은 $1$부터 $N$까지의 번호를 가지고 있다,

알고리즘 학원에서는 학생의 수준을 나타내기 위해 레이팅 시스템을 사용하는데, 모든 학생은 자신만의 레이팅을 갖고 있고, $i$번 학생의 레이팅은 $a_i$로 나타낼 수 있다.

지환이는 학원 수강생의 레이팅 상승을 위해 $2$명의 학생을 골라 몰래 과외를 해주려고 한다. 그런데 수강생은 자기와 번호가 너무 많이 차이 나거나 너무 적게 차이 나는 학생을 싫어한다. 따라서 $i$번 학생은 자기와의 번호 차이가 $l_i$ 이상 $r_i$ 이하인 학생들과만 과외를 하려고 할 것이다.

위의 조건을 만족하면서 레이팅의 차이가 최대가 되도록 $2$명의 학생을 고를 때, 그때의 레이팅의 차를 구하여라.

첫 번째 줄에는 알고리즘 학원의 학생 수 $N$이 주어진다. ($2 \le N \le 200\,000$)

두 번째 줄부터 $N+1$번째 줄까지는 학생의 정보가 주어진다. $i+1$번째 줄에는 세 정수 $a_i$, $l_i$, $r_i$가 공백으로 구분되어 주어지는데, 이는 $i$번 학생의 레이팅이 $a_i$이고, 자기와의 번호 차이가 $l_i$ 이상 $r_i$ 이하인 학생들과만 과외를 하려고 한다는 의미이다. ($1 \le a_i \le 10^9$, $1 \le l_i \le r_i \le N$)

문제의 조건을 모두 만족하면서 레이팅의 차이가 최대가 되도록 $2$명의 학생을 고를 때, 그때의 레이팅의 차를 출력한다.

만약 조건을 만족하도록 $2$명의 학생을 고를 수 없다면 $-1$을 출력한다.