A delivery rider serves m delivery zones connected by a circular road. The zones are numbered from 1 to m in clockwise order.

Each zone is adjacent to the zones immediately before and after it in circular order. Therefore, zone 1 is adjacent to zones 2 and m, and zone m is adjacent to zones m - 1 and 1.

The rider starts in zone 1 and receives a list of delivery stops. These stops must be visited in the given order.

Due to local roads and traffic, leaving zone i and reaching either adjacent zone takes zoneTimes.get(i - 1) minutes.

Return the minimum total travel time required to complete all deliveries.

Class

DeliveryRoutePlanner

Method

minimumTravelTime

public long minimumTravelTime(List<Integer> zoneTimes, List<Integer> deliveryStops)

• zoneTimes.get(i - 1) is the time required to leave zone i and reach either adjacent zone.
• deliveryStops contains the zones that must be visited, in order.
• Returns the minimum total travel time in minutes.

Rules

• The rider begins in zone 1.
• The delivery stops must be visited in the given order.
• After completing a delivery, the rider starts the next trip from that zone.
• The rider may move clockwise or counterclockwise around the circular road.
• Moving through multiple zones costs the sum of the travel times for every zone that the rider leaves.
• No travel time is charged for the destination zone unless the rider later leaves it.
• Travel times may be asymmetric because the cost is determined by the zone being left.
• If the rider is already in the next delivery zone, the required travel time is 0.
• Completing a delivery takes no additional time.
• The rider does not need to return to zone 1.
• The supplied lists must not be modified.

Constraints

• m = zoneTimes.size()
• 2 ≤ m ≤ 100,000
• q = deliveryStops.size()
• 1 ≤ q ≤ 100,000
• 0 ≤ i < m for zoneTimes.get(i)
• 1 ≤ zoneTimes.get(i) ≤ 100,000
• 0 ≤ i < q for deliveryStops.get(i)
• 1 ≤ deliveryStops.get(i) ≤ m
• All travel-time calculations must use 64-bit integer arithmetic.
• The solution must run in O(m + q) time.

Examples

Example 1

minimumTravelTime(zoneTimes = [4, 1, 7, 2, 5], deliveryStops = [4, 2, 2, 5])

Output: 23

The rider travels from zone 1 to zone 4 via zone 5, taking 4 + 5 = 9 minutes.

Traveling from zone 4 to zone 2 through zone 3 takes 2 + 7 = 9 minutes. The repeated stop in zone 2 requires no travel. Finally, traveling from zone 2 to zone 5 through zone 1 takes 1 + 4 = 5 minutes.

Therefore, the minimum total time is 9 + 9 + 0 + 5 = 23 minutes.

Example 2

minimumTravelTime(zoneTimes = [8, 3, 6, 2, 7, 4], deliveryStops = [6, 3, 1])

Output: 30

The minimum travel times for the three trips are 8, 13, and 9 minutes.

Example 3

minimumTravelTime(zoneTimes = [5, 2, 8], deliveryStops = [1, 1, 3, 3])

Output: 5

The first two deliveries are already in zone 1. The rider then travels directly from zone 1 to zone 3 in 5 minutes. The final delivery is also in zone 3.