There are n cards on the table. Each card has two numbers written on it — the card rank and the serial number. You should form a deck:

• You take cards one by one in any order from the cards remaining on the table;
• You are not allowed to take two cards of the same rank one after another. The first card can have any rank;
• Starting from the second card, you need to pay one coin for each card on the table having the rank which is strictly within the range between the current card and the previous card ranks;
• All the cards having serial number which is less than or equal to the current card serial number are removed from the cards remaining on the table after the payment;
• Starting from the third card, the "the force direction changing" condition must be fulfilled, i.e. let us denote the current, the previous and pre-previous selected cards ranks by a, b and c. If b < min(a, c) or b > max(a, c) then the condition is fulfilled;
• The deck forming is terminated when it's not possible to select a card from the cards remaining on the table.

Calculate the total cost in coins of all possible decks. Two decks are considered to be different if there is a card that enters one deck and does not enter another. However, different cards can have the same rank and serial number.