TABY - TABTABTAB


Have you ever used a text editor like notepad ++ or sublime? In the text editor software, several lines can be selected at once so that in 1x the tab key on the keyboard is pressed, all lines will move forward. Or press Shift Tab 1x then all the selected lines will be backward together. Selection of rows must be carried out sequentially (for example selecting rows 1 to line 5) and should not select lines that are jumped (not consecutive).

Input

Input begins with a T representing a testcase (1 <= T <= 100) and is followed by N (amount of text, 1<=N<=100000) inside the text editor. Each text in the text editor has an initial tab position. The line after N is the starting tab position of each text. Two Lines after N is the tab position the goal is to reach.

Output

Each time the Tab key or Shift Tab key is pressed will count as one press of the key. Find the minimum number of Tab or Shift Tab presses to reach the destination.

Example

Input:
1
3
1 2 3
3 4 5

Output:
2

hide comments
suhash: 2021-12-13 03:38:58

Test cases are weak. My O(N^2) and O(N * log N) solution both run in 0.01 sec (the first one should time out). Also, the constraints section is incomplete. Please provide a range for the initial and final positions of the text.

Also, this is supposed to be a harder version of https://www.spoj.com/problems/C1TABOVI/ (please provide credits in the resources section). But in it's current state (weak tests), it's exactly the same.

Last edit: 2021-12-13 03:42:18
majid: 2021-04-28 09:56:51

more test case plz


Added by:wibit
Date:2020-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All