Anya and Smartphone

题意翻译

题目描述 安雅购买了一只带有Berdroid操作系统的智能手机。智能手机菜单中有n个应用，每个应用程序都有其自己的图标。每个应用的图标都在相应的屏幕上，一个屏幕包含ķ个图标。第1个应用到第k个应用的图标位于第一个屏幕上，从第（k + 1）个至第2k个应用在第二个屏幕上，依次类推（最后屏幕可以是部分为空） 。 开始的时候，智能手机显示的屏幕是第一个屏幕，为了去启动第t个屏幕上的应用，安雅需要做如下的手势：首先是连续切换屏幕t-1次，其次是点击第t个屏幕上的那个应用程序。 在应用程序启动以后，屏幕会重新返回到第1个屏幕。也就是说，如果你要启动下一个程序，必须又要重头来过。 所有应用程序的编号是从1到n。我们知道所有屏幕中每个应用程序的位置。但是Berdroid是智能系统，他会根据用户实际的使用情况，自动把使用次数最多的应用放到最前面。变化规则是这样的，当一个应用程序启动以后，系统会自动的将该程序的图标位置和他前面的那个应用程序的图标互换位置（可能会导致图标不在原来的屏幕上）。当然了，如果那个被启动的应用程序已经在第一个位置上了，就不需要再更换位置了。 如果你已经知道安雅启动某些应用程序的顺序，请你来计算他需要多个手势（切换一个屏幕或者点击一个应用程序图标都算作一次手势）来完成这些任务。 注意，一个应用可以发起多次。 输入格式： 输入的第一行包含三个整数n，m，k（1≤n，m，k≤10^5),n表示应用程序的数量，m表示将要启动的应用程序的数量，k表示每个屏幕上图标的数量。 第二行包含n个整数，分别为a1，a2，...，an，表示初始的时候应用程序图标的顺序，按照这个顺序放到一个个屏幕中去。ai是每个应用程序的编号，ai不会重复。 第三行包含m个整数b1，b2，...，bm（1≤bm≤n），表示安雅计划启动的应用程序的编号。一个应用程序可能会启动多次。 输出格式 输出一个整数，表示安雅完成这些任务需要使用的手势次数。 输入样例1： 8 3 3 1 2 3 4 5 6 7 8 7 8 1 输入样例2： 5 4 2 3 1 5 2 4 4 4 4 4 输出样例1： 7 输出样例2： 8 提示 在第一个样例中的起始位置是（123）（456）（78），也就是，在第一个屏幕包含应用程序1，2，3的图标，第二个屏幕包含图标4，5，6，第三个屏幕包含图标7,8。 应用7启动后，我们得到新的图标位置-（123）（457）（68）。这过程需要3次手势。 应用8被启动后，我们得到的位置（123）（457）（86），要启动它安雅需要使用3次手势。 应用1启动后，图标菜单中的排列没有变化，要启动它安雅需要1次手势。 所以说，总共需要3+3+1=7次手势。

题目描述

Anya has bought a new smartphone that uses Berdroid operating system. The smartphone menu has exactly $ n $ applications, each application has its own icon. The icons are located on different screens, one screen contains $ k $ icons. The icons from the first to the $ k $ -th one are located on the first screen, from the $ (k+1) $ -th to the $ 2k $ -th ones are on the second screen and so on (the last screen may be partially empty). Initially the smartphone menu is showing the screen number $ 1 $ . To launch the application with the icon located on the screen $ t $ , Anya needs to make the following gestures: first she scrolls to the required screen number $ t $ , by making $ t-1 $ gestures (if the icon is on the screen $ t $ ), and then make another gesture — press the icon of the required application exactly once to launch it. After the application is launched, the menu returns to the first screen. That is, to launch the next application you need to scroll through the menu again starting from the screen number $ 1 $ . All applications are numbered from $ 1 $ to $ n $ . We know a certain order in which the icons of the applications are located in the menu at the beginning, but it changes as long as you use the operating system. Berdroid is intelligent system, so it changes the order of the icons by moving the more frequently used icons to the beginning of the list. Formally, right after an application is launched, Berdroid swaps the application icon and the icon of a preceding application (that is, the icon of an application on the position that is smaller by one in the order of menu). The preceding icon may possibly be located on the adjacent screen. The only exception is when the icon of the launched application already occupies the first place, in this case the icon arrangement doesn't change. Anya has planned the order in which she will launch applications. How many gestures should Anya make to launch the applications in the planned order? Note that one application may be launched multiple times.

输入输出格式

输入格式

The first line of the input contains three numbers $ n,m,k $ ( $ 1<=n,m,k<=10^{5} $ ) — the number of applications that Anya has on her smartphone, the number of applications that will be launched and the number of icons that are located on the same screen. The next line contains $ n $ integers, permutation $ a_{1},a_{2},...,a_{n} $ — the initial order of icons from left to right in the menu (from the first to the last one), $ a_{i} $ — is the id of the application, whose icon goes $ i $ -th in the menu. Each integer from $ 1 $ to $ n $ occurs exactly once among $ a_{i} $ . The third line contains $ m $ integers $ b_{1},b_{2},...,b_{m}(1<=b_{i}<=n) $ — the ids of the launched applications in the planned order. One application may be launched multiple times.

输出格式

Print a single number — the number of gestures that Anya needs to make to launch all the applications in the desired order.

输入输出样例

输入样例 #1

8 3 3
1 2 3 4 5 6 7 8
7 8 1

输出样例 #1

7

输入样例 #2

5 4 2
3 1 5 2 4
4 4 4 4

输出样例 #2

8

说明

In the first test the initial configuration looks like $ (123)(456)(78) $ , that is, the first screen contains icons of applications $ 1,2,3 $ , the second screen contains icons $ 4,5,6 $ , the third screen contains icons $ 7,8 $ . After application $ 7 $ is launched, we get the new arrangement of the icons — $ (123)(457)(68) $ . To launch it Anya makes $ 3 $ gestures. After application $ 8 $ is launched, we get configuration $ (123)(457)(86) $ . To launch it Anya makes $ 3 $ gestures. After application $ 1 $ is launched, the arrangement of icons in the menu doesn't change. To launch it Anya makes $ 1 $ gesture. In total, Anya makes $ 7 $ gestures.

题意翻译

题目描述 安雅购买了一只带有Berdroid操作系统的智能手机。智能手机菜单中有n个应用，每个应用程序都有其自己的图标。每个应用的图标都在相应的屏幕上，一个屏幕包含ķ个图标。第1个应用到第k个应用的图标位于第一个屏幕上，从第（k + 1）个至第2k个应用在第二个屏幕上，依次类推（最后屏幕可以是部分为空） 。 开始的时候，智能手机显示的屏幕是第一个屏幕，为了去启动第t个屏幕上的应用，安雅需要做如下的手势：首先是连续切换屏幕t-1次，其次是点击第t个屏幕上的那个应用程序。 在应用程序启动以后，屏幕会重新返回到第1个屏幕。也就是说，如果你要启动下一个程序，必须又要重头来过。 所有应用程序的编号是从1到n。我们知道所有屏幕中每个应用程序的位置。但是Berdroid是智能系统，他会根据用户实际的使用情况，自动把使用次数最多的应用放到最前面。变化规则是这样的，当一个应用程序启动以后，系统会自动的将该程序的图标位置和他前面的那个应用程序的图标互换位置（可能会导致图标不在原来的屏幕上）。当然了，如果那个被启动的应用程序已经在第一个位置上了，就不需要再更换位置了。 如果你已经知道安雅启动某些应用程序的顺序，请你来计算他需要多个手势（切换一个屏幕或者点击一个应用程序图标都算作一次手势）来完成这些任务。 注意，一个应用可以发起多次。 输入格式： 输入的第一行包含三个整数n，m，k（1≤n，m，k≤10^5),n表示应用程序的数量，m表示将要启动的应用程序的数量，k表示每个屏幕上图标的数量。 第二行包含n个整数，分别为a1，a2，...，an，表示初始的时候应用程序图标的顺序，按照这个顺序放到一个个屏幕中去。ai是每个应用程序的编号，ai不会重复。 第三行包含m个整数b1，b2，...，bm（1≤bm≤n），表示安雅计划启动的应用程序的编号。一个应用程序可能会启动多次。 输出格式 输出一个整数，表示安雅完成这些任务需要使用的手势次数。 输入样例1： 8 3 3 1 2 3 4 5 6 7 8 7 8 1 输入样例2： 5 4 2 3 1 5 2 4 4 4 4 4 输出样例1： 7 输出样例2： 8 提示 在第一个样例中的起始位置是（123）（456）（78），也就是，在第一个屏幕包含应用程序1，2，3的图标，第二个屏幕包含图标4，5，6，第三个屏幕包含图标7,8。 应用7启动后，我们得到新的图标位置-（123）（457）（68）。这过程需要3次手势。 应用8被启动后，我们得到的位置（123）（457）（86），要启动它安雅需要使用3次手势。 应用1启动后，图标菜单中的排列没有变化，要启动它安雅需要1次手势。 所以说，总共需要3+3+1=7次手势。