For a sequence S of positive integers and positive integers k and l, S is said to belong to level (k,l) when one of the following conditions is satisfied:

* The length of S is 1, and its only element is k.
* There exist sequences T_1,T_2,...,T_m (m \geq l) belonging to level (k-1,l) such that the concatenation of T_1,T_2,...,T_m in this order coincides with S.



Note that the second condition has no effect when k=1, that is, a sequence belongs to level (1,l) only if the first condition is satisfied.

Given are a sequence of positive integers A_1,A_2,...,A_N and a positive integer L. Find the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the following condition:

* There exists a positive integer K such that the sequence A_i,A_{i+1},...,A_j belongs to level (K,L).

Constraints

* 1 \leq N \leq 2 \times 10^5
* 2 \leq L \leq N
* 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N L
A_1 A_2 ... A_N


Output

Print the number of subsequences A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) that satisfy the condition.

Examples

Input

9 3
2 1 1 1 1 1 1 2 3


Output

22


Input

9 2
2 1 1 1 1 1 1 2 3


Output

41


Input

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2


Output

31
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NavigableSet;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        static final int INF = (int) 2e9;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int l = in.nextInt();
            TreeSet<TaskF.Item> itemsByPos = new TreeSet<>(new Comparator<TaskF.Item>() {

                public int compare(TaskF.Item o1, TaskF.Item o2) {
                    return o1.pos - o2.pos;
                }
            });
            TreeSet<TaskF.Item> itemsByVal = new TreeSet<>(new Comparator<TaskF.Item>() {

                public int compare(TaskF.Item o1, TaskF.Item o2) {
                    int z = o1.value - o2.value;
                    if (z == 0) z = o1.pos - o2.pos;
                    return z;
                }
            });
            for (int i = 0; i < n; ++i) {
                TaskF.Item item = new TaskF.Item();
                item.pos = i;
                item.value = in.nextInt();
                item.choicesIfFirst = 1;
                item.choicesIfLast = 1;
                itemsByPos.add(item);
                itemsByVal.add(item);
            }
            long res = n;
            TaskF.Item[] segment = new TaskF.Item[n + 1];
            int[] sumStarts = new int[n + 1];
            TaskF.Item[] newItems = new TaskF.Item[n + 1];

            while (!itemsByVal.isEmpty()) {
                int segmentSize = 0;
                TaskF.Item left = itemsByVal.first();
                NavigableSet<TaskF.Item> after = itemsByPos.tailSet(left, true);
                for (TaskF.Item item : after) {
                    if (item.value != left.value) {
                        break;
                    }
                    segment[segmentSize++] = item;
                }
                for (int i = 0; i < segmentSize; ++i) {
                    TaskF.Item s = segment[i];
                    if (!itemsByVal.remove(s)) throw new RuntimeException();
                    if (!itemsByPos.remove(s)) throw new RuntimeException();
                }
                if (segmentSize < l) {
                    TaskF.Item sentinel = new TaskF.Item();
                    sentinel.pos = left.pos;
                    sentinel.value = INF;
                    itemsByPos.add(sentinel);
                    continue;
                }
                sumStarts[0] = 0;
                for (int i = 0; i < segmentSize; ++i) {
                    sumStarts[i + 1] = sumStarts[i] + segment[i].choicesIfFirst;
                }
                for (int i = l - 1; i < segmentSize; ++i) {
                    long ways = segment[i].choicesIfLast * (long) sumStarts[i + 2 - l];
                    res += ways;
                }
                int newCount = segmentSize / l;
                for (int i = 0; i < newCount; ++i) {
                    newItems[i] = new TaskF.Item();
                    newItems[i].value = left.value + 1;
                    newItems[i].pos = left.pos + i;
                }
                for (int i = 0; i + l <= segmentSize; ++i) {
                    int got = (segmentSize - i) / l;
                    newItems[newCount - got].choicesIfFirst += segment[i].choicesIfFirst;
                }
                for (int i = l - 1; i < segmentSize; ++i) {
                    int got = (i + 1) / l;
                    newItems[got - 1].choicesIfLast += segment[i].choicesIfLast;
                }
                sumStarts[0] = 0;
                for (int i = 0; i < newCount; ++i) {
                    sumStarts[i + 1] = sumStarts[i] + newItems[i].choicesIfFirst;
                }
                for (int i = l - 1; i < newCount; ++i) {
                    long ways = newItems[i].choicesIfLast * (long) sumStarts[i + 2 - l];
                    res -= ways;
                }
                for (int i = 0; i < newCount; ++i) {
                    itemsByVal.add(newItems[i]);
                    itemsByPos.add(newItems[i]);
                }
            }
            out.println(res);
        }

        static class Item {
            int pos;
            int value;
            int choicesIfFirst;
            int choicesIfLast;

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

