409865: GYM103811 I Inno Per Gli Sconfitti

Jane used to work as a cashier at a grocery store in Hackerland. Due to COVID-19, she has lost the job. Therefore, she has decided to chase her long time dream by teaming up with a few friends to form a band called "Dear Jane".

The band recently released a new song "Inno Per Gli Sconfitti". To promote the song, they are planning to visit 3 different schools in Hackerland. There are $$$N$$$ schools in Hackerland, numbered from $$$1$$$ to $$$N$$$. The selected schools will be decided by public voting on Instagram. Each school has a separate post that Instagram users can give Like to. The 3 schools that receive the most Likes will be selected. If there are ties, then the tieing schools will have equal chance of getting selected.

Jane actually wants her 3 favourite schools $$$X, Y, Z$$$ to be selected so she decided to rig the poll by buying Likes and end the poll immediately after that. She already knows how many Likes each school has. School $$$i$$$ currently has $$$A_i$$$ likes. In order to make her 3 favourite schools to have strictly more Likes than the other schools, what is the minimum number of Likes she has to buy? The ranking among the 3 favourite schools do not matter.

The first line contains an integer $$$N$$$ – the number of schools. ($$$4 \le N \le 100000$$$)

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ – the current number of Likes each school has. ($$$0 \le A_i \le 10^6$$$).

The third line contains 3 distinct integers $$$X, Y, Z$$$ – the indices of Jane's favourite schools. ($$$1 \le X, Y, Z \le N$$$)

Output a single integer, the minimum number of Likes that Jane needs to buy.

5
10 20 10 15 10
1 3 5

33

9
11 9 1 12 14 3 5 10 7
8 4 5

2

In the first sample, Jane needs to buy 11 Likes for each of her favourite school to beat the 4th place school which has 10 Likes.