codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

270B.md (2368B)


      1 Source: https://codeforces.com/problemset/problem/270/B
      2 
      3 B. Multithreading
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages.
     22 
     23 Recent actions shows a list of *n* different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time.
     24 
     25 Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at the *i*-th place in the list there is a thread that was at the *a**i*-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages.
     26 
     27 Help Emuskald find out the number of threads that surely have new messages. A thread *x* surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold:
     28 
     29 1. thread *x* is not updated (it has no new messages);
     30 2. the list order 1, 2, ..., *n* changes to *a*1, *a*2, ..., *a**n*.
     31 
     32 Input
     33 
     34 The first line of input contains an integer *n*, the number of threads (1 ≤ *n* ≤ 105). The next line contains a list of *n* space-separated integers *a*1, *a*2, ..., *a**n* where *a**i* (1 ≤ *a**i* ≤ *n*) is the old position of the *i*-th thread in the new list. It is guaranteed that all of the *a**i* are distinct.
     35 
     36 Output
     37 
     38 Output a single integer — the number of threads that surely contain a new message.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 5  
     46 5 2 1 3 4
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 3  
     59 1 2 3
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 0
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 4  
     72 4 3 2 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 3
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages.
     84 
     85 In the second test case, there may be no new messages at all, since the thread order hasn't changed.
     86 
     87 In the third test case, only thread 1 can contain no new messages.