Technoblade decided to play a coin game with Skeppy to pass the time. Each of them brought $$$N$$$ coins from home and now they have placed all $$$2N$$$ coins in a row. Each coin has a value that can range from $$$1$$$ real to $$$10^4$$$ reais, the Brazilian currency.
The game consists of taking the leftmost or rightmost coin and taking exactly $$$1$$$ for yourself. In the end, your score is the sum of the values of your coins. Whoever has more is considered the champion.
As Technoblade is the oldest, he starts with a $$$1$$$ real advantage, but in return he must be the first to play.
Skeppy doesn't like to think about strategies, so he just takes the larger of the left and right coins. If both have the same value, he prefers the one on the right.
As a spectator, you want to try to predict the game. You must guess who will win the game, or if Techno can force a tie, assuming that Technoblade, unlike Skeppy, plays optimally.
If Technoblade is the champion, also print his sequence of moves. In case there are many sequences that guarantee victory, print the one with the smallest lexicographic value (see output).
The first line contains an integer $$$N$$$. Followed by a line with $$$2N$$$ integers from $$$1$$$ to $$$10000$$$, representing the coins from left to right, already set up for the start of the game. It is guaranteed that $$$1 \leq N \leq 2500$$$.
If Technoblade is doomed to defeat, print only ":(", without quotes.
If Technoblade cannot win, but can force a tie, print only "tie", without quotes.
If he can win, print "TECHNOBLADE NEVER DIES!" on the first line, without quotes. Then print another line with $$$N$$$ characters "L" or "R". The i-th character determines whether Techno should take the coin from the left or the right in that round. If there are many possible sequences, print the smallest lexicographically.
2 1 10 10 1
TECHNOBLADE NEVER DIES! LL
3 10 1000 1 1 1 1
TECHNOBLADE NEVER DIES! RLL
2 1 10 1 10
TECHNOBLADE NEVER DIES! LL
| UNICAMP Selection Contest 2023 |
|---|
| Закончено |
