We’re preparing your current view and syncing the latest data.
Xenia lives in a city with n houses arranged in a circle. Houses are numbered from 1 to n clockwise. Xenia has m friends who live in different houses. She wants to visit her friends in a given order. Starting at house 1, she needs to move along the ringroad clockwise visiting each friend's house in the specified order.
Given the sequence of friends' house numbers, find the total time (in seconds) Xenia needs to visit all the friends in order. Moving from house x to house y clockwise costs (y - x) if y >= x, otherwise (n - x + y) seconds.
Xenia visits houses in the order given, starting from house 1.
The first line contains two integers n and m (1 ≤ n, m ≤ 10^5), the number of houses and the number of friends. The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ n), the sequence of houses to visit.
Output a single integer — the total time Xenia needs to visit all friends in order.
1 ≤ n, m ≤ 10^5 1 ≤ ai ≤ n
Example 1
Input
4 3 3 2 3
Output
6
Explanation
Xenia starts at house 1: Move from 1 to 3: 2 seconds Move from 3 to 2: 3 seconds (wrap around) Move from 2 to 3: 1 second Total time = 6 seconds