This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has n passenger seats, seat i can be occupied only by a participant from the city ai.

Today the bus has completed m trips, each time bringing n participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence a1, a2, ..., an repeated m times).

After that some teams were formed, each consisting of k participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no k neighboring participants from the same city.

Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected.

Input

The first line contains three integers n, k and m (1 ≤ n ≤ 105, 2 ≤ k ≤ 109, 1 ≤ m ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105), where ai is the number of city, person from which must take seat i in the bus. 

Output

Output the number of remaining participants in the line.

Examples

Input

4 2 5
1 2 3 1


Output

12


Input

1 9 10
1


Output

1


Input

3 2 10
1 2 1


Output

0

Note

In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.Deque;
import java.util.ArrayDeque;
import java.io.InputStream;

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

    static class DTeamsFormation {
        int[] arr;
        int n;
        long k;
        long m;

        Deque<int[]> make_quee() {
            Deque<int[]> res = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                if (res.size() == 0) {
                    res.add(new int[]{arr[i], 1});
                } else {
                    if (res.getLast()[0] == arr[i]) {
                        res.getLast()[1]++;
                        if (res.getLast()[1] == k) res.pollLast();
                    } else {
                        res.add(new int[]{arr[i], 1});
                    }
                }
                if (res.size() != 0 && res.getLast()[1] == k) res.pollLast();
            }
            return res;
        }

        long remaining(Deque<int[]> q) {
            long sum = 0;
            for (int i[] : q) sum += i[1];
            return sum;
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            n = in.scanInt();
            k = in.scanInt();
            m = in.scanInt();
            arr = new int[n];
            in.scanInt(arr);
            Deque<int[]> a = make_quee();

            long single = remaining(a);
            if (single == 0) {
                out.println(0);
                return;
            }


            while (a.size() > 1 && a.getFirst()[0] == a.getLast()[0]) {
                int num = a.getFirst()[0];
                int aa = a.getFirst()[1];
                int bb = a.getLast()[1];
                a.pollLast();
                a.pollFirst();
                if (((aa + bb) % k) != 0) a.add(new int[]{num, (int) ((aa + bb) % k)});
            }


            long dou = remaining(a);


            if (a.size() == 0) {
                out.println(0);
                return;
            } else if (a.size() > 1) {
                out.println((m - 1) * dou + single);
            } else {
                long e = (a.getFirst()[1] * m) % k;
//            out.println(e);
                if (e != 0) {
                    out.println(e + single - dou);
                } else {
                    out.println(0);
                }
            }


        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public void scanInt(int[] A) {
            for (int i = 0; i < A.length; i++) A[i] = scanInt();
        }

    }
}

