408731: GYM103274 I Introducing Teleporting Machine

Nlogonia is connected to Linealonia by a directed linear highway, this is, vehicles can travel from Nlogonia to Linealonia but not in the other way, and the highway does not have any curves, it is a straight line. The highway has $$$N$$$ cities, there are no two cities in the same place and, they are numbered from $$$1$$$ to $$$N$$$ in such way that if city $$$j$$$ is after city $$$i$$$ when you take the highway if $$$j > i$$$ for all $$$i, j \leq N$$$, city $$$N$$$ is Linealonia.

The next year Linealonia will host a programming contest, each city in the highway will send a team to compete in the contest, the cost it takes for a team to go from one city to another is equal to the distance between the two cities. Linealonia has agreed to pay for the travel expenses of all the teams, so they want to find a way to minimize the total cost for all the teams to get to city $$$N$$$. To achieve this, they will build a teleport machine to connect two cities, the only restriction for this machine is that the two cities it connects should be at most at $$$K$$$ Km distance away, and if it connects city $$$i$$$ and $$$j$$$, city $$$j$$$ should be as far as possible from $$$i$$$, considering the $$$K$$$ km restriction. The main advantage of building this machine is that if a team decides to use the machine the cost to travel between the two cities the machine connects will be a constant $$$T$$$, hopefully reducing the total cost for Linealonia.

Can you help Linealonia find what two cities should the machine connect in order to reduce the total cost to gather all the teams for their programming contest?

The first line of input contains three integer numbers separated by a space $$$N$$$, $$$K$$$ and $$$T$$$, ($$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 10^9$$$, $$$1 \leq T \leq 10^9$$$) representing the number of cities in the highway, the maximum distance between the two cities where the teleport machine can be built, and the cost of using the machine. The second and last line of input contains $$$N$$$ integer numbers separated by a space, the $$$i$$$-th number represents the km where the $$$i$$$-th city is in the highway. No contiguous cities (i.e. $$$i$$$ and $$$i + 1$$$) are more than $$$10^9$$$ Km apart and the machine can always be built

If the total cost to gather all the teams at Linealonia can be reduced building the teleport machine print a line with three integer numbers, $$$i$$$, $$$j$$$, and $$$c$$$, representing the cities $$$i$$$ and $$$j$$$ the machine should connect $$$j > i$$$, and the minimum cost $$$c$$$ achieved, if there are more than two pairs where the minimum cost can be achieved building the machine, print the one with the minimum $$$i$$$. If the total cost can not be reduced building the teleport machine print -1.

4 6 6
2 6 10 13

-1

4 15 1
2 6 10 13

2 4 9